재귀함수 정복하기

1. 재귀함수란?

재귀함수는 자기 자신을 다시 호출하는 함수를 말합니다.

어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.
"재귀함수가 뭔가요?"
"잘 들어보게. 옛날에 산 꼭대기에 현자가 있었어. 질문엔 모두 지혜롭게 대답 해 주었지.
그런데 어느날, 그 선인에게 한 선비가 찾아와서 물었어.
"재귀함수가 뭔가요?"
"잘 들어보게. 옛날에 산 꼭대기...

2. 재귀함수의 구성요소

1. Base Case (종료 조건)
2. : 더 이상 재귀 호출을 하지 않아야 할 조건
3. Recursive Case (자기 자신을 호출하는 부분)
4. : 문제를 더 작게 쪼개서 자기 자신을 호출

3-1. 예제 1: 팩토리얼 (n!)

n! = n × (n-1)!
조건: 1! = 1

def factorial(n):
    if n == 1:         # 종료 조건
        return 1
    return n * factorial(n - 1)  # 재귀 호출

print(factorial(5))  # 출력: 120

3-2. 예제 2: 피보나치 수열

f(n) = f(n-1) + f(n-2)
조건: f(0) = 0, f(1) = 1

def fibonacci(n):
    if n == 0: return 0
    if n == 1: return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(6))  # 출력: 8

⚠️ 단점: 같은 계산을 반복해서 속도가 느림 → 나중에 DP(메모이제이션) 적용 필요

3-3.  예제 3: 하노이의 탑

세 개의 기둥과 여러 개의 원판이 있을 때, 모든 원판을 규칙에 따라 다른 기둥으로 옮기는 문제

규칙:

• 한 번에 한 개의 원판만 이동
• 더 작은 원판 위에 큰 원판을 놓을 수 없음

def hanoi(n, start, end, aux):
    if n == 1:
        print(f"{start} → {end}")
        return
    hanoi(n - 1, start, aux, end)
    print(f"{start} → {end}")
    hanoi(n - 1, aux, end, start)

hanoi(3, 'A', 'C', 'B')

출력:

A → C  
A → B  
C → B  
A → C  
B → A  
B → C  
A → C

4.  재귀 vs 반복

항목	재귀함수	반복문 (for, while)
코드 길이	짧고 직관적	길어질 수 있음
성능	느릴 수 있음 (호출 오버헤드)	일반적으로 더 빠름
사용 예시	DFS, 트리 탐색, 하노이의 탑 등	단순 반복 작업에 적합

5.  재귀가 필요한 이유?

• 트리 구조 탐색 (예: 파일 시스템, 조직도)
• 백트래킹 (예: N-Queen 문제)
• DFS 탐색
• 문제를 나눠 푸는 Divide and Conquer