재귀 함수 (Recursion)

# 재귀 함수 (Recursion)

## 재귀란?

함수가 **자기 자신을 호출**하는 것입니다. 큰 문제를 같은 구조의 작은 문제로 나눌 때 유용합니다.

```c
void countdown(int n) {
    if (n == 0) {
        printf("발사!\n");
        return;         // 기저 조건 (재귀 종료)
    }
    printf("%d...\n", n);
    countdown(n - 1);  // 자기 자신을 호출
}

int main() {
    countdown(3);
    // 출력: 3... 2... 1... 발사!
    return 0;
}
```

---

## 재귀의 두 가지 필수 요소

1. **기저 조건 (Base Case)**: 재귀를 멈추는 조건 — 없으면 무한 재귀
2. **재귀 단계 (Recursive Step)**: 자기 자신을 더 작은 입력으로 호출

```c
int factorial(int n) {
    // 1. 기저 조건
    if (n <= 1) return 1;

// 2. 재귀 단계 (더 작은 문제로 위임)
    return n * factorial(n - 1);
}
```

---

## 예제 1: 팩토리얼 (n!)

```
5! = 5 × 4! = 5 × 4 × 3! = 5 × 4 × 3 × 2 × 1 = 120
```

```c
#include <stdio.h>

int factorial(int n) {
    if (n <= 1) return 1;           // 0! = 1! = 1
    return n * factorial(n - 1);
}

int main() {
    for (int i = 0; i <= 7; i++) {
        printf("%d! = %d\n", i, factorial(i));
    }
    return 0;
}
```

출력:
```
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
```

---

## 재귀 호출 시각화

`factorial(4)` 호출 과정:

```
factorial(4)
  └─ 4 * factorial(3)
         └─ 3 * factorial(2)
                └─ 2 * factorial(1)
                       └─ return 1
                ← 2 * 1 = 2
         ← 3 * 2 = 6
  ← 4 * 6 = 24
```

---

## 예제 2: 피보나치 수열

```
F(0)=0, F(1)=1, F(n) = F(n-1) + F(n-2)
```

```c
int fibonacci(int n) {
    if (n == 0) return 0;   // 기저 조건 1
    if (n == 1) return 1;   // 기저 조건 2
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    for (int i = 0; i <= 10; i++) {
        printf("F(%2d) = %d\n", i, fibonacci(i));
    }
    return 0;
}
```

> ⚠️ 이 구현은 같은 값을 수없이 반복 계산합니다. n이 커지면 매우 느립니다.  
> (예: `fibonacci(40)`은 수억 번의 함수 호출 발생)

---

## 스택 오버플로우 주의

재귀는 함수 호출마다 **스택 메모리**를 사용합니다. 기저 조건이 없거나 너무 깊이 재귀하면 **스택 오버플로우**가 발생합니다.

```c
// ❌ 기저 조건 없음 → 무한 재귀 → 스택 오버플로우
void infinite(int n) {
    printf("%d\n", n);
    infinite(n + 1);   // 절대 멈추지 않음
}
```

일반적으로 재귀 깊이는 **수천 ~ 수만 단계** 이상이 되면 위험합니다.

---

## 재귀 vs 반복문

| 항목 | 재귀 | 반복문 |
|------|------|--------|
| 코드 간결성 | 간결할 수 있음 | 더 명시적 |
| 성능 | 함수 호출 오버헤드 | 일반적으로 빠름 |
| 메모리 | 스택 사용 | 상수 메모리 |
| 적합한 경우 | 트리, 분할정복, 수학적 정의 | 단순 반복 |

```c
// 팩토리얼 — 반복문 버전 (더 빠름)
int factorial_loop(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}
```

---

## 예제: 거듭제곱 계산

```c
#include <stdio.h>

double power(double base, int exp) {
    if (exp == 0) return 1.0;              // 기저 조건: n^0 = 1
    if (exp < 0)  return 1.0 / power(base, -exp);  // 음수 지수
    return base * power(base, exp - 1);
}

int main() {
    printf("2^10  = %.0f\n",  power(2, 10));   // 1024
    printf("3^4   = %.0f\n",  power(3, 4));    // 81
    printf("2^-3  = %.4f\n",  power(2, -3));   // 0.1250
    return 0;
}
```

---

재귀 함수 (Recursion)

// COMMENTS

ON THIS PAGE