C언어 재귀함수 (Recursion)
요약
C언어 재귀함수의 개념과 동작 원리를 알아봅니다. 기저 조건, 함수 호출 체인, 팩토리얼, 다중 재귀 등 정보처리기사 실기에 출제되는 재귀 개념을 정리합니다.
재귀함수 핵심 정리
함수와 조건문을 먼저 알고 오면 이해가 쉽습니다. 아래는 이 페이지에서 배울 내용을 미리 정리한 표입니다.
| 개념 | 설명 | 예시 |
|---|---|---|
| 재귀함수 | 함수가 자기 자신을 호출하는 함수 | fn(n-1) |
| 기저 조건 | 재귀 호출을 멈추는 조건 | if (n <= 1) return 1; |
| 함수 호출 체인 | 함수가 다른 함수를 호출하며 이어지는 구조 | r100() → r10() → r1() |
| 호출 스택 | 함수 호출 정보가 쌓이는 스택 메모리 (접시를 쌓듯 위로 쌓이고, 위부터 꺼냄) | 호출할 때 쌓이고, 반환할 때 제거 |
재귀함수란? 쌩기초
재귀함수(Recursive Function)란 함수가 자기 자신을 다시 호출하는 함수입니다.
위 코드에서 fn 함수 안에서 다시 fn(n - 1)을 호출합니다. 이것이 재귀입니다.
함수 호출 체인 기초
재귀를 이해하기 전에, 먼저 함수가 다른 함수를 호출하는 구조를 알아보겠습니다. 함수에서 배운 것처럼, 함수는 다른 함수를 호출할 수 있습니다.
이 코드는 재귀는 아니지만, 함수가 함수를 호출하는 체인 구조입니다.
호출 순서 추적하기
함수 호출 체인은 안쪽 함수부터 계산해야 합니다. 바깥 함수는 안쪽 함수의 반환값을 기다리기 때문입니다.
| 단계 | 함수 | 계산 | 반환값 |
|---|---|---|---|
| 1 | r1() | 4 | 4 |
| 2 | r10() | 30 + r1() = 30 + 4 | 34 |
| 3 | r100() | 200 + r10() = 200 + 34 | 234 |
출력: 234
재귀함수의 동작 원리 기초
함수 호출 체인에서 호출하는 함수가 자기 자신이면 재귀함수입니다.
팩토리얼 예제
팩토리얼(Factorial)은 1부터 n까지의 모든 수를 곱한 값입니다. 5! = 5 x 4 x 3 x 2 x 1 = 120
재귀 호출 추적하기
fn(5)를 호출하면 다음과 같이 동작합니다.
1단계: 호출이 쌓이는 과정 (기저 조건에 도달할 때까지)
2단계: 반환값이 돌아오는 과정 (기저 조건에서부터 역순으로)
| 호출 | 계산 | 반환값 |
|---|---|---|
fn(1) | 기저 조건 (n <= 1) | 1 |
fn(2) | 2 * fn(1) = 2 * 1 | 2 |
fn(3) | 3 * fn(2) = 3 * 2 | 6 |
fn(4) | 4 * fn(3) = 4 * 6 | 24 |
fn(5) | 5 * fn(4) = 5 * 24 | 120 |
출력: 120
실기 문제 풀이 전략 심화
재귀함수 문제 풀이 순서
- 기저 조건 확인: 조건문(
if)에서 어떤 값을 반환하는지 확인 - 재귀 호출 파악:
return문에서 자기 자신을 어떻게 호출하는지 확인 - 호출 트리 작성: 기저 조건에 도달할 때까지 호출을 펼치기
- 역순 계산: 기저 조건의 반환값부터 시작하여 위로 계산
복잡한 재귀: 두 번 이상 자기 자신을 호출하는 경우
재귀 호출이 두 번 이상 있는 경우, 각 호출의 반환값을 모두 계산해야 합니다.
이 함수는 gamja(n-1)과 gamja(n-3) 두 개의 재귀 호출을 합니다.
gamja(7) 호출 추적
gamja(7)부터 펼쳐 내려갑니다. 각 호출을 gamja(n-1) + gamja(n-3)으로 분해하고, 기저 조건(n <= 1)에 도달하면 멈춥니다.
같은 값이 여러 번 등장하지만, 한 번만 계산하면 나머지는 같은 결과입니다.
거꾸로 계산
모든 호출이 기저 조건에 도달했으므로, 가장 작은 값부터 거꾸로 계산합니다.
| 호출 | 계산 | 결과 |
|---|---|---|
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