C언어 재귀함수 (Recursion)
코딩C언어
읽는데 6분 소요
처음 쓰여진 날: 2026-02-10
마지막 수정일: 2026-02-10
조회수: 8
요약
C언어 재귀함수의 개념과 동작 원리를 알아봅니다. 기저 조건, 함수 호출 체인, 팩토리얼 등 정보처리기사 실기에 출제되는 재귀 개념을 정리합니다.
키워드 체크
다음은 정보처리기사 실기에서 재귀함수와 관련하여 출제된 키워드입니다.
| 키워드 | 의미 | 출제 회차 |
|---|---|---|
if (a <= 1) return 1; | 기저 조건 (재귀 종료 조건) | 20년3회, 22년1회 |
fn(n - 1) | 재귀 호출 (자기 자신 호출) | 20년3회, 22년1회, 23년3회 |
fn(n - 1) + fn(n - 2) | 다중 재귀 호출 | 23년3회 |
재귀함수 핵심 정리
| 개념 | 설명 | 예시 |
|---|---|---|
| 재귀함수 | 함수가 자기 자신을 호출하는 함수 | fn(n-1) |
| 기저 조건 | 재귀 호출을 멈추는 조건 | if (n <= 1) return 1; |
| 함수 호출 체인 | 함수가 다른 함수를 호출하며 이어지는 구조 | r100() → r10() → r1() |
| 호출 스택 | 함수 호출 정보가 쌓이는 스택 메모리 | 호출할 때 쌓이고, 반환할 때 제거 |
재귀함수란?
재귀함수(Recursive Function) 란 함수가 자기 자신을 다시 호출하는 함수입니다.
c
코드 하이라이팅 중...
위 코드에서 fn 함수 안에서 다시 fn(n - 1)을 호출합니다. 이것이 재귀입니다.
기저 조건이 없으면 무한 반복됩니다
재귀함수는 반드시 멈추는 조건(기저 조건)이 있어야 합니다. 기저 조건이 없으면 함수가 끝없이 자기 자신을 호출하다가 스택 오버플로우(Stack Overflow)가 발생합니다.
함수 호출 체인
재귀를 이해하기 전에, 먼저 함수가 다른 함수를 호출하는 구조를 알아보겠습니다.
c
코드 하이라이팅 중...
이 코드는 재귀는 아니지만, 함수가 함수를 호출하는 체인 구조입니다.
호출 순서 추적하기
함수 호출 체인은 안쪽 함수부터 계산해야 합니다. 바깥 함수는 안쪽 함수의 반환값을 기다리기 때문입니다.
text
코드 하이라이팅 중...
| 단계 | 함수 | 계산 | 반환값 |
|---|---|---|---|
| 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
c
코드 하이라이팅 중...
재귀 호출 추적하기
fn(5)를 호출하면 다음과 같이 동작합니다.
1단계: 호출이 쌓이는 과정 (기저 조건에 도달할 때까지)
text
코드 하이라이팅 중...
2단계: 반환값이 돌아오는 과정 (기저 조건에서부터 역순으로)
text
코드 하이라이팅 중...
| 호출 | 계산 | 반환값 |
|---|---|---|
fn(1) | 기저 조건 (a <= 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문에서 자기 자신을 어떻게 호출하는지 확인 - 호출 트리 작성: 기저 조건에 도달할 때까지 호출을 펼치기
- 역순 계산: 기저 조건의 반환값부터 시작하여 위로 계산
복잡한 재귀: 두 번 이상 자기 자신을 호출하는 경우
재귀 호출이 두 번 이상 있는 경우, 각 호출의 반환값을 모두 계산해야 합니다.
c
코드 하이라이팅 중...
이 함수는 gamja(n-1)과 gamja(n-3) 두 개의 재귀 호출을 합니다.
표로 정리하기
복잡한 재귀는 작은 값부터 표로 정리하면 실수를 줄일 수 있습니다.
n <= 1이면 n을 반환합니다
기저 조건에서 1이 아니라 n을 반환합니다. n이 0이면 0, n이 1이면 1, n이 -1이면 -1을 반환합니다. 기저 조건의 반환값을 꼼꼼히 확인하세요.
| n | 기저 조건? | 계산 | 결과 |
|---|---|---|---|
| -1 | O (n <= 1) | return -1 | -1 |
| 0 | O (n <= 1) | return 0 | 0 |
| 1 | O (n <= 1) | return 1 | 1 |
| 2 | X | gamja(1) + gamja(-1) = 1 + (-1) | 0 |
| 3 | X | gamja(2) + gamja(0) = 0 + 0 | 0 |
| 4 | X | gamja(3) + gamja(1) = 0 + 1 | 1 |
| 5 | X | gamja(4) + gamja(2) = 1 + 0 | 1 |
| 6 | X | gamja(5) + gamja(3) = 1 + 0 | 1 |
| 7 | X | gamja(6) + gamja(4) = 1 + 1 | 2 |
gamja(7) 의 출력: 2
복잡한 재귀 풀이 팁
재귀 호출이 두 번 이상인 문제는 작은 값부터 차례대로 표를 채워 나가세요. 이미 계산한 값을 참조하면 빠르게 풀 수 있습니다.