재귀 추적
재귀 디버깅은 종료와 축소 우선 검토
결과가 틀릴 때는 계산식보다 호출이 끝나는지, 매번 더 작은 문제로 이동하는지부터 추적합니다.
base case
smaller input
call depth
기저 조건이 먼저다
n == 0처럼 더 이상 자기 자신을 부르지 않는 조건이 모든 경로에 필요합니다.
입력은 작아져야 한다
factorial(n - 1)처럼 다음 호출이 반드시 종료 조건에 가까워져야 합니다.
반복 호출은 따로 본다
피보나치처럼 같은 입력을 반복 계산하면 메모이제이션이나 반복문을 검토합니다.
01 · 입장
인자 값을 기록합니다.
02 · 분기
기저 조건을 통과합니다.
03 · 호출
더 작은 입력을 넘깁니다.
04 · 복귀
반환값을 합칩니다.
깊이가 입력 크기와 함께 커지면 작은 예제에서는 맞아도 큰 입력에서 스택 오버플로우가 날 수 있습니다.