재귀·기저 사례·호출 스택
팩토리얼로 작은 문제의 반환을 기다리는 구조와 종료 조건을 익힙니다.
함수가 자기 자신을 부르는 재귀는 읽는 순서가 낯설 수 있습니다. 목표는 호출이 내려가는 과정과 결과가 돌아오는 과정을 따로 추적하는 것입니다. 함수의 반환과 종료 설명을 복습하세요.
개념과 약속
재귀는 현재 문제를 더 작은 같은 종류의 문제에 맡깁니다. 기저 사례는 더 호출하지 않고 직접 답을 주는 가장 작은 입력입니다. 팩토리얼 n!은 1부터 n까지의 곱이고 0!=1입니다. n≥1일 때 n!=n×(n-1)!를 사용합니다.
호출할 때 현재 함수의 인자·지역 상태·돌아올 위치가 호출 스택에 보존됩니다. 스택은 마지막에 넣은 것이 먼저 나오는 LIFO 구조입니다. 가장 깊은 호출이 끝나면 바로 전에 기다리던 호출부터 반환합니다. Python은 재귀 깊이에 제한이 있으므로 큰 n을 재귀로 직접 처리하기보다 반복 또는 명시적인 스택을 검토해야 합니다.
재귀의 기다림과 반환
3×factorial(2)를 계산하기 위해 반환을 기다린다. 최종 결과를 계산한다. 각 단계의 값과 전환 이유를 비교합니다.
자료구조·알고리즘 · 상태와 관계
재귀의 기다림과 반환
위 호출은 아래 호출의 답이 돌아올 때까지 기다립니다.
화살표는 작은 문제의 호출이며, 아래 설명은 반대 방향으로 돌아오는 결과 순서입니다. 강조한 기저 사례가 추가 호출을 멈춥니다.
이 예의 조건
- 본문과 전체 도표의 예를 따라 3 호출부터 3으로 반환까지 진행합니다.
관계도의 보충 설명
| 구분 | 전체 도표의 내용 |
|---|---|
| 관계 설명 | factorial(3)은 factorial(2)의 반환을, factorial(2)는 factorial(1)의 반환을 기다린다. factorial(1)의 답 1이 돌아오면 2를 만들고 이어 6을 만든다. |
| 관찰·상황 | 값·보충 정보 | 변화·이유 |
|---|---|---|
| 3 호출 3×factorial(2)를 계산하기 위해 반환을 기다린다. |
|
|
| 2 호출 2×factorial(1)을 계산하기 위해 반환을 기다린다. |
|
|
| 기저 사례 factorial(1)=1을 반환한다. |
|
|
| 2로 반환 기다리던 곱셈을 계산한다. |
|
|
| 3으로 반환 최종 결과를 계산한다. |
|
|
재귀의 기다림과 반환
3×factorial(2)를 계산하기 위해 반환을 기다린다. 최종 결과를 계산한다. 각 단계의 값과 전환 이유를 비교합니다.
자료구조·알고리즘 · 상태와 관계
재귀의 기다림과 반환
위 호출은 아래 호출의 답이 돌아올 때까지 기다립니다.
화살표는 작은 문제의 호출이며, 아래 설명은 반대 방향으로 돌아오는 결과 순서입니다. 강조한 기저 사례가 추가 호출을 멈춥니다.
이 예의 조건
- 본문과 전체 도표의 예를 따라 3 호출부터 3으로 반환까지 진행합니다.
관계도의 보충 설명
| 구분 | 전체 도표의 내용 |
|---|---|
| 관계 설명 | factorial(3)은 factorial(2)의 반환을, factorial(2)는 factorial(1)의 반환을 기다린다. factorial(1)의 답 1이 돌아오면 2를 만들고 이어 6을 만든다. |
| 관찰·상황 | 값·보충 정보 | 변화·이유 |
|---|---|---|
| 3 호출 3×factorial(2)를 계산하기 위해 반환을 기다린다. |
|
|
| 2 호출 2×factorial(1)을 계산하기 위해 반환을 기다린다. |
|
|
| 기저 사례 factorial(1)=1을 반환한다. |
|
|
| 2로 반환 기다리던 곱셈을 계산한다. |
|
|
| 3으로 반환 최종 결과를 계산한다. |
|
|
손으로 상태 추적하기
| 내려가는 호출 | 기다리는 계산 | 돌아오는 결과 |
|---|---|---|
| factorial(3) | 3 × factorial(2) | 6 |
| factorial(2) | 2 × factorial(1) | 2 |
| factorial(1) | 기저 사례 | 1 |
호출은 3→2→1, 반환은 1→2→6 순서입니다. 화면에 쓴 숫자 순서와 실제 곱셈 완료 순서는 다릅니다.
직접 실행하기
아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.
def factorial(n):
if n < 0:
raise ValueError("nonnegative n required")
if n <= 1:
return 1
return n * factorial(n - 1)
print(factorial(3))
print(factorial(0))
try:
factorial(-1)
except ValueError:
print("음수 거부")실행 결과:
6
1
음수 거부왜 맞고 언제 끝나는가
기저 사례 0과 1은 정의에 맞습니다. n-1의 답이 맞다고 가정하면 n을 곱해 n!을 얻습니다. 음수가 아닌 입력은 호출마다 n이 줄어 1 또는 0에 도달합니다. 음수는 잘못된 무한 하강을 시작하기 전에 거부합니다.
비용과 적용 범위
n에 비례하는 호출·곱셈을 하며 호출 스택은 O(n) 깊이입니다. 실제 정수의 비트 수가 커져 큰 수 곱셈은 상수 비용이 아니므로 비트 복잡도와 단순 연산 횟수를 구분합니다. 재귀를 썼다는 이유만으로 빠른 것은 아닙니다.
스스로 풀어 보기
- factorial(4)에서 각각의 호출이 기다리는 계산과 반환값을 쓰세요.
- 기저 사례를 n==1만으로 바꾸면 입력 0에 어떤 일이 생기나요?
힌트
- 4×3!에서 시작해 1!까지 내려갑니다.
- 0에서 n-1은 -1입니다.
해설
- 4×3!, 3×2!, 2×1!가 기다리고 1,2,6,24가 돌아옵니다.
- 0을 처리하지 못해 음수 오류가 나거나, 음수 검사가 없다면 재귀 깊이 오류까지 내려갑니다. 기저 사례는 입력 계약의 경계를 포함해야 합니다.
흔한 오해
재귀 호출 뒤의 문장은 즉시 실행되지 않습니다. 호출한 작은 문제가 반환해야 이어서 실행합니다.
복습과 다음 연결
병합 정렬은 두 작은 문제를 풀고 합칩니다. DFS는 호출 스택을 명시적인 스택으로 바꾸어 생각할 수 있습니다.