재귀 함수

이 Part에서 다루는 것

• 재귀 함수의 본질(자기 호출 + 기저 사례 + 점진적 수렴)
• 스택 프레임 관점에서 본 재귀 동작 원리
• 대표 예제: 카운트다운, 팩토리얼, 유클리드 호제법(GCD)
• 재귀 디버깅 방법과 자주 발생하는 실수

학습 목표

• 재귀 함수를 작성할 때 반드시 들어가야 하는 2요소(기저 사례, 수렴 규칙)를 설명할 수 있다.
• 재귀 호출의 실행/복귀 순서를 스택 관점으로 추적할 수 있다.
• 팩토리얼과 GCD를 재귀로 구현하고, 반복문 버전과 장단점을 비교할 수 있다.

---

재귀 함수란?

핵심 정의

• 재귀 함수는 함수가 자기 자신을 다시 호출하는 함수입니다.
• 하지만 “자기 호출”만으로는 부족합니다. 아래 2가지가 동시에 필요합니다.
  1. 기저 사례(Base Case): 더 내려가지 않고 즉시 반환하는 조건
  2. 수렴 규칙(Progress): 호출할수록 기저 사례에 가까워지는 변화

왜 스택 오버플로우가 나는가

• 함수가 호출될 때마다 스택에 스택 프레임이 쌓입니다.
• 재귀는 함수가 끝나기 전에 다시 자신을 호출하므로 프레임이 연속 누적됩니다.
• 기저 사례가 없거나 수렴이 잘못되면 프레임이 무한히 쌓여 스택 오버플로우가 납니다.

Func(3)
 -> Func(2)
   -> Func(1)
     -> Func(0)  // base case
     <- return
   <- return
 <- return

기본 예제(카운트다운)

void Func(int a)
{
    if (a <= 0)  // base case
        return;

    std::cout << a << '\n';
    Func(a - 1); // progress: a가 0에 가까워짐
}

실행 흐름(Func(3)):

1. 3 출력 -> Func(2)
2. 2 출력 -> Func(1)
3. 1 출력 -> Func(0)
4. a <= 0 조건으로 종료

---

팩토리얼(Factorial)

수학 정의를 그대로 코드로 옮기기

• 수학 정의:
  • n! = n * (n-1)!
  • 0! = 1
• 재귀는 이런 “큰 문제 = 더 작은 같은 문제” 형태를 코드로 옮길 때 강합니다.

구현

long long Factorial(int n)
{
    if (n < 0)
        return 0; // 입력 정책 예시: 음수는 0 반환(또는 예외)

    if (n <= 1)
        return 1;

    return static_cast<long long>(n) * Factorial(n - 1);
}

호출/복귀 순서 이해(Factorial(4))

• 내려갈 때: 4 * F(3) -> 3 * F(2) -> 2 * F(1)
• 올라올 때: F(1)=1 -> F(2)=2 -> F(3)=6 -> F(4)=24

주의:

• 정수 범위가 작아 오버플로우가 빠르게 발생합니다(예: 13!부터 int 초과).

---

유클리드 알고리즘(GCD)

아이디어

• GCD(a, b) = GCD(b, a % b)
• 나머지를 반복적으로 줄여 가면 결국 b == 0이 되고, 그때의 a가 최대공약수입니다.

예시:

GCD(1071, 1029)
= GCD(1029, 42)
= GCD(42, 21)
= GCD(21, 0)
= 21

구현

int Gcd(int a, int b)
{
    if (b == 0)
        return a >= 0 ? a : -a; // 부호 정규화

    return Gcd(b, a % b);
}

포인트:

• 매우 짧고 명확한 재귀 예제라 실무/면접에서 자주 등장합니다.

---

재귀를 잘 쓰는 기준

• 부분 문제가 원래 문제와 같은 형태인가?
• 종료 조건이 명확한가?
• 각 호출에서 문제가 작아지는지 증명 가능한가?

직관 비유:

• 러시아 인형처럼 “열어보면 같은 구조가 반복”되는 문제는 재귀와 잘 맞습니다.
• 트리/그래프 탐색(DFS)이 대표 사례입니다.

---

디버깅/주의점 요약

항목	핵심
기저 사례 누락	무한 호출 -> 스택 오버플로우
수렴 실패	n-1 대신 n+1 같은 실수로 종료 불가
값 범위	팩토리얼 등은 오버플로우 주의
디버깅	F11로 진입 + Call Stack 창으로 깊이/복귀 순서 확인
대안 선택	깊이가 매우 깊으면 반복문/명시적 스택을 고려

체크 질문 (스스로 답해보기)

• 재귀 함수가 안전하려면 어떤 2가지 조건이 반드시 필요한가?
• Factorial에서 오버플로우 위험을 줄이려면 어떤 타입/정책이 필요한가?
• DFS를 재귀 대신 반복문(스택)으로 바꾸는 기준은 무엇인가?

---