C언어 재귀 함수
🔥 매회 출제 (priority 3)
🌱 왜 배우나
러시아 인형 마트료시카를 떠올려 보자. 큰 인형을 열면 똑같이 생긴 작은 인형이 나오고, 그걸 또 열면 더 작은 인형이 나온다. 마지막에는 더 이상 열 수 없는 가장 작은 인형이 등장한다.
재귀가 딱 이 모양이다. 폴더 안에 폴더가 들어 있는 구조를 탐색하거나, 팩토리얼(n × (n-1) × … × 1)처럼 “나 자신의 작은 버전으로 정의되는 문제”는 반복문으로 짜면 코드가 복잡해진다. 대신 “나는 한 단계만 처리하고 나머지는 더 작아진 나에게 맡기자”라고 말하는 편이 훨씬 간결하다. 이 말을 문법으로 만든 게 재귀 함수다.
📖 핵심 개념
재귀 함수(Recursive Function)는 자기 자신을 호출하는 함수다. 함수 안에서 그 함수를 다시 부른다.
이때 반드시 종료 조건(Base Case)이 있어야 한다. 종료 조건이란 “여기까지 오면 더 이상 나를 부르지 말고 바로 답을 돌려줘”라고 못 박는 부분이다. 이게 없으면 함수가 끝없이 자기를 불러 호출 스택이 넘쳐 버린다. 이 사고가 스택 오버플로우다.
호출 스택(Call Stack)은 함수가 호출될 때마다 기록이 한 칸씩 쌓이고, 함수가 끝나면 한 칸씩 빠지는 공간이다. 시험에서 재귀 문제가 나오면 호출 트리를 그리는 게 핵심이다. 호출 트리는 함수가 자기 자신을 어떻게 계속 불렀는지 나뭇가지처럼 그린 그림이다. 가장 깊은 종료 조건부터 거꾸로 올라오며 값을 채워 넣으면 답이 나온다.
🔍 시각화
팩토리얼 호출 과정: factorial(4)
호출 방향(내려감) 반환 방향(올라옴)
factorial(4) → 4 × 6 = 24
└─ factorial(3) → 3 × 2 = 6
└─ factorial(2) → 2 × 1 = 2
└─ factorial(1) → 1 ← 종료 조건(여기서 멈춤)
피보나치 호출 트리: f(5)
f(5)
┌───┴───┐
f(4) f(3)
┌──┴──┐ ┌──┴──┐
f(3) f(2) f(2) f(1)=1
┌──┴──┐ │ │
f(2) f(1) 1 1
│ =1
1
→ 같은 값(예: f(2)) 을 여러 번 중복 계산함
↔️ 이웃 개념 구분
- 재귀 vs 반복문: 재귀는 함수가 스스로를 다시 부름. 반복문은 같은 코드 블록을 되풀이. 같은 답을 낼 수 있지만, 어떤 문제는 재귀 쪽이 훨씬 짧고 읽기 쉽다.
- 종료 조건 vs 재귀 호출: 종료 조건은 “여기서 멈춰”. 재귀 호출은 “아직 아니야, 더 작은 문제로 바꿔서 나를 다시 불러”.
🔑 핵심 용어
- 종료 조건(Base Case): 재귀 호출을 멈추는 지점. 빠지면 무한 재귀로 스택 오버플로우 발생
- 재귀 호출(Recursive Case): 자기 자신을 다시 불러 문제를 더 작은 크기로 나누는 부분
- 호출 스택(Call Stack): 함수 호출 기록(스택 프레임)이 한 칸씩 쌓였다 빠지는 공간
- 꼬리 재귀(Tail Recursion): 재귀 호출이 함수의 맨 마지막 연산인 형태. 일부 컴파일러가 반복문처럼 최적화해 준다
✅ 스스로 가르쳐보기
재귀 함수를 처음 듣는 친구에게 설명한다면 어떻게 말하시겠어요? 마트료시카, 거울 속의 거울, 폴더 안의 폴더 같은 비유 하나로 한 문장 정의를 만들어 보세요.
체크포인트 — 아래를 말로 풀어 설명할 수 있는지 확인해 보세요.
- 종료 조건이 없으면 어떤 일이 벌어지는지, 그리고 왜 그렇게 되는지
- 호출은 아래로 내려가는데 값은 왜 위로 올라오면서 계산되는지
- 피보나치 재귀가 같은 값을 여러 번 다시 계산하는 이유
factorial(4)를 직접 호출 트리로 따라가면서 최종 답을 구해 볼 수 있는지
🎯 기출 포인트
- 2025-1회: Java 재귀 함수 결과 추적(답: 20). C와 같은 방식으로 풀면 된다
- 매회 1~2문항: 재귀 출력 결과 쓰기는 가장 자주 나오는 유형
- 트레이싱 팁: 호출 트리를 그린 뒤 종료 조건부터 거꾸로 값을 채워 올라오면 실수를 줄인다
- 주의:
f(n-1) + f(n-2)같은 이중 재귀는 호출 횟수가 기하급수적으로 늘어남
🔗 연결 개념
- Java 재귀함수
pg-data-structure-003