Python 재귀 함수 (Recursion)
요약
Python 재귀 함수의 개념과 동작 원리를 알아봅니다. 기저 조건, 함수 호출 체인, 팩토리얼, 다중 재귀 등 정보처리기사 실기에 출제되는 재귀 개념을 정리합니다.
재귀 함수 핵심 정리
함수와 조건문을 먼저 알고 오면 이해가 쉽습니다. 아래는 이 페이지에서 배울 내용을 미리 정리한 표입니다.
| 개념 | 설명 | 예시 |
|---|---|---|
| 재귀 함수 | 함수가 자기 자신을 호출하는 함수 | 함수 f 안에서 f를 다시 부름 |
| 기저 조건 | 재귀 호출을 멈추는 조건 | if n == 1: return 1 |
| 함수 호출 체인 | 함수가 다른 함수를 호출하며 이어지는 구조 | r100() → r10() → r1() |
아래에서 하나씩 설명합니다.
재귀 함수란? 쌩기초
재귀 함수(Recursive Function)란 함수가 자기 자신을 다시 호출하는 함수입니다.
위 코드에서 f 함수 안에서 다시 f(n - 1)을 호출합니다. 이것이 재귀입니다.
재귀 함수의 두 가지 부분
재귀 함수는 항상 다음 두 부분으로 이루어집니다.
| 부분 | 설명 |
|---|---|
| 기저 조건 (base case) | 더 이상 자기 자신을 호출하지 않고 즉시 반환하는 조건 |
| 재귀 호출 (recursive case) | 기저 조건에 가까워지도록 변형된 입력으로 자기 자신을 다시 호출. 예를 들어 n - 1처럼 n을 1씩 줄여서 n == 1에 도달하게 합니다 |
기저 조건이 없으면 어떻게 될까요?
함수 호출 체인 기초
재귀를 이해하기 전에, 먼저 함수가 다른 함수를 호출하는 구조를 알아보겠습니다. 함수에서 배운 것처럼, 함수는 다른 함수를 호출할 수 있습니다. 이렇게 함수들이 사슬처럼 이어지는 것을 호출 체인(chain)1이라고 합니다.
이 코드는 재귀는 아니지만, 함수가 함수를 호출하는 체인 구조입니다. 만약 r100, r10, r1이 전부 같은 함수라면 어떨까요? 자기 자신을 계속 호출하는 재귀 함수가 됩니다.
호출 순서 추적하기
함수 호출 체인은 안쪽 함수부터 계산해야 합니다. 바깥 함수는 안쪽 함수의 반환값을 기다리기 때문입니다.
| 단계 | 함수 | 계산 | 반환값 |
|---|---|---|---|
| 1 | r1() | 4 | 4 |
| 2 | r10() | 30 + r1() = 30 + 4 | 34 |
| 3 | r100() | 200 + r10() = 200 + 34 | 234 |
출력: 234
재귀 함수의 동작 원리 기초
함수 호출 체인에서 호출하는 함수가 자기 자신이면 재귀 함수입니다.
1부터 n까지의 합
def는 함수를 만드는 키워드, return은 결과값을 돌려주는 키워드입니다. 자세한 내용은 함수 페이지를 참고하세요.
재귀 호출 추적하기
total(5)를 호출하면 다음과 같이 동작합니다.
1단계: 호출이 쌓이는 과정 (기저 조건에 도달할 때까지)
2단계: 반환값이 돌아오는 과정 (기저 조건에서부터 역순으로)
| 호출 | 계산 | 반환값 |
|---|---|---|
total(1) | 기저 조건 (n == 1)2 | 1 |
total(2) | 2 + total(1) = 2 + 1 | 3 |
total(3) | 3 + total(2) = 3 + 3 | 6 |
total(4) | 4 + total(3) = 4 + 6 | 10 |
total(5) | 5 + total(4) = 5 + 10 | 15 |
출력: 15
팩토리얼 예제
팩토리얼(Factorial)은 1부터 n까지의 모든 수를 곱한 값입니다. 5!(5 팩토리얼)은 수학에서 5부터 1까지 차례로 곱하라는 뜻으로, 느낌표(!)는 팩토리얼을 나타내는 수학 기호입니다. 5! = 5 x 4 x 3 x 2 x 1 = 120
"재귀 함수란?" 섹션의 첫 예제도 이 팩토리얼 함수입니다.
total(5)를 추적했던 것과 같은 방식으로 따라가 봅시다. 다른 점은 +가 *로 바뀐 것뿐입니다.
거꾸로 계산하면:
| 호출 | 계산 | 반환값 |
|---|---|---|
f(1) | 기저 조건 (n == 1) | 1 |
f(2) | 2 * f(1) = 2 * 1 | 2 |
f(3) | 3 * f(2) = 3 * 2 | 6 |
f(4) | 4 * f(3) = 4 * 6 | 24 |
f(5) | 5 * f(4) = 5 * 24 | 120 |
출력: 120
실기 문제 풀이 전략 심화
재귀 함수 문제 풀이 순서
- 기저 조건 확인:
if문에서 어떤 값을 반환하는지 확인 - 재귀 호출 파악:
return문에서 자기 자신을 어떻게 호출하는지 확인 - 호출 추적(호출 트리) 작성3: 기저 조건에 도달할 때까지 호출을 펼치기
- 역순 계산: 기저 조건의 반환값부터 시작하여 위로 계산
복잡한 재귀: 두 번 이상 자기 자신을 호출하는 경우
재귀 호출이 두 번 이상 있는 경우, 각 호출의 반환값을 모두 계산해야 합니다.
이 함수는 gamja(n - 1)과 gamja(n - 3) 두 개의 재귀 호출을 합니다.
gamja(7) 호출 추적
기저 조건에 닿을 때까지 각 호출을 분해합니다. gamja(7)부터 시작하여 gamja(n - 1) + gamja(n - 3) 형태로 한 줄씩 펼쳐 내려가고, n <= 1인 기저 조건에 도달하면 멈춥니다. 왼쪽(n - 1)을 먼저 분해하고, 오른쪽(n - 3)은 나중에 분해합니다.
시험에서 풀 때, gamja(2)를 한 번 계산해 놓으면 다시 등장할 때 같은 값을 쓰면 됩니다. (실제 프로그램은 매번 다시 계산합니다.)
거꾸로 계산
모든 호출이 기저 조건에 도달했으므로, 가장 작은 값부터 거꾸로 계산합니다.
| 호출 | 계산 | 결과 |
|---|---|---|
gamja(-1) | 기저 조건 (n <= 1) | -1 |
gamja(0) | 기저 조건 (n <= 1) | 0 |
gamja(1) | 기저 조건 (n <= 1) | 1 |
gamja(2) | gamja(1) + gamja(-1) = 1 + (-1) | 0 |
gamja(3) | gamja(2) + gamja(0) = 0 + 0 | 0 |
gamja(4) | gamja(3) + gamja(1) = 0 + 1 | 1 |
gamja(5) | gamja(4) + gamja(2) = 1 + 0 | 1 |
gamja(6) | gamja(5) + gamja(3) = 1 + 0 | 1 |
gamja(7) | gamja(6) + gamja(4) = 1 + 1 | 2 |
gamja(7)의 출력: 2
예를 들어 total(5) 재귀 함수는 다음 반복문과 같은 결과를 냅니다.