재귀 디버깅은 계산식보다 종료와 축소를 먼저 본다
결과가 틀리면 최종 값부터 보지 말고, 호출이 안전하게 끝나는지부터 순서대로 추적합니다.
01
기저 조건에 도달하는가
가장 작은 입력에서 바로 반환하는지 확인합니다.
02
입력이 작아지는가
n - 1처럼 다음 호출이 종료 조건에 가까워지는지 봅니다.
03
호출 깊이가 과한가
입력 크기와 스택 깊이가 함께 커지면 반복 전환을 검토합니다.
04
같은 입력을 반복하는가
중복 호출이 보이면 메모이제이션이나 DP가 필요할 수 있습니다.
입장인자 기록
분기base/step 확인
호출더 작은 입력
복귀반환값 결합
기저 조건과 축소가 맞는데도 느리다면, 계산식보다 중복 호출을 먼저 의심합니다.