재귀 함수는 같은 문제를 더 작게 다시 호출한다
핵심은 반복 호출 자체가 아니라, 멈추는 조건과 매번 작아지는 입력이 함께 있는지입니다.
한 문장 정의
함수가 자기 자신을 호출해 원래 문제와 같은 모양의 더 작은 문제를 해결합니다.
factorial(n) = n * factorial(n - 1)
base case
더 이상 호출하지 않고 바로 반환하는 조건
recursive step
입력을 줄여 같은 함수를 다시 부르는 단계
stack cost
호출이 깊어질수록 쌓이는 실행 문맥
팩토리얼
n!을 n * (n - 1)!로 줄입니다.
트리 탐색
왼쪽과 오른쪽 하위 트리를 같은 방식으로 방문합니다.
피보나치
같은 값이 반복 계산되어 메모이제이션이 필요할 수 있습니다.
재귀를 볼 때는 “자기 호출”보다 “언제 멈추고, 어떻게 작아지는가”를 먼저 확인합니다.