더 호출하지 않는 경우
n이 0 또는 1일 때처럼 바로 결과를 반환하는 조건이 있어야 합니다.
if (n <= 1)
재귀 축소 모델
재귀를 안전하게 쓰려면 종료 조건과 한 단계 줄어드는 입력이 함께 보여야 합니다.
작아진 입력으로 호출
현재 문제를 n - 1, 왼쪽 절반처럼 더 작은 같은 구조로 넘깁니다.
f(n - 1)
돌아온 결과 사용
작은 문제의 결과를 현재 단계의 계산과 합쳐 최종 답을 만듭니다.
n * f(n-1)
호출 스택과 중복 계산
깊은 재귀는 스택을 많이 쓰고 피보나치처럼 중복 호출이 많을 수 있습니다.
stack frames
팩토리얼n!은 n과 (n - 1)!의 곱으로 정의되어 재귀 구조가 정의에 그대로
드러납니다.
피보나치단순 재귀는 같은 값을 반복 계산하므로 메모이제이션이나 반복문이
필요할 수 있습니다.
반복 비교반복문이 더 단순하고 안전하면 실전에서는 재귀보다 반복을
선택합니다.