기저 조건
모든 경로가 멈추는 조건에 도달해야 합니다.
재귀 유지 조건
safe shape문제 축소
호출마다 입력이 더 작거나 단순해져야 합니다.
스택 깊이
깊이가 입력 크기만큼 커지면 스택 비용을 봅니다.
중복 계산
피보나치처럼 같은 하위 문제가 반복되면 캐시를 고려합니다.
base
shrink
cost
choose
재귀 코드는 종료 조건과 문제 축소가 선명해야 합니다. 호출 깊이와 중복 계산이 커지면 반복이나 메모이제이션을 검토합니다.
모든 경로가 멈추는 조건에 도달해야 합니다.
호출마다 입력이 더 작거나 단순해져야 합니다.
깊이가 입력 크기만큼 커지면 스택 비용을 봅니다.
피보나치처럼 같은 하위 문제가 반복되면 캐시를 고려합니다.
핵심 질문 “언제 멈추는가”, “정말 작아지는가”, “같은 일을 반복하는가” 세 가지에 답하면 재귀와 반복 중 어느 쪽이 적절한지 빠르게 보입니다.