기저 조건
더 호출하지 않고 바로 반환하는 조건을 명확히 둡니다.
Recursion Review
재귀는 끝나는 조건과 작아지는 호출이 함께 있어야 한다
자기 자신을 부르는 구조는 간결하지만, 종료 조건과 문제 축소가 흐리면 스택 오버플로우나 중복 계산으로 이어집니다.
종료
기저 조건이 먼저 보이는가
축소
호출 인자가 답에 가까워지는가
비용
호출 깊이와 중복 계산이 감당 가능한가
재귀 단계
원래 문제보다 작아진 입력으로 자기 자신을 호출합니다.
호출 깊이
입력이 커질수록 스택 프레임이 얼마나 쌓이는지 생각합니다.
중복 계산
피보나치처럼 같은 값을 반복하면 반복문이나 메모이제이션을 봅니다.
호출은 쌓이고, 반환은 역순으로 풀린다
5!
5 x 4!
4!
4 x 3!
3!
3 x 2!
2!
2 x 1!
1!
return 1