재귀 함수

1. 재귀 함수란?

정의:

• 재귀 함수는 자기 자신을 호출하는 함수입니다.
• 재귀는 문제를 더 작은 단위로 나누어 풀 때 적합합니다.
• 알고리즘적으로 동일한 논리를 반복적으로 적용하여 문제를 해결합니다.

---

2. 재귀 함수 기본 예제

코드 예제

void Func(int a) {
    if (a == 0) {
        return;
    }
    std::cout << a << std::endl;
    Func(a - 1);
}

라인별 분석

1. void Func(int a)

   • 매개변수 int a를 받는 함수 정의입니다.
   • 반환값은 없으며, 함수 내부에서 자기 자신을 호출하는 재귀적 구조를 가집니다.

2. if (a == 0)

   • 종료 조건(Base Case): a가 0일 경우, 함수 실행을 종료합니다.
   • 종료 조건이 없으면 스택 오버플로우(Stack Overflow)가 발생할 수 있습니다.

3. return;

   • 조건이 충족되었을 때 실행을 멈추고 호출한 함수로 돌아갑니다.

4. std::cout << a << std::endl;

   • 현재 a의 값을 출력합니다.
   • 재귀 호출이 진행될 때마다 함수가 호출된 시점의 값을 출력합니다.

5. Func(a - 1);

   • a 값을 1 감소시켜 재귀적으로 자신을 호출합니다.

---

실행 과정

• 예를 들어 Func(3) 호출 시:
  1. a = 3: 3 출력 후, Func(2) 호출.
  2. a = 2: 2 출력 후, Func(1) 호출.
  3. a = 1: 1 출력 후, Func(0) 호출.
  4. a = 0: 조건문에 의해 실행 종료.

출력 결과

3
2
1

---

3. 팩토리얼 계산을 위한 재귀 함수

코드 예제

int Factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * Factorial(n - 1);
}

라인별 분석

1. int Factorial(int n)

   • n!을 계산하기 위한 함수입니다.
   • 입력값 n이 정수이며 반환값도 정수입니다.

2. if (n <= 1)

   • 종료 조건(Base Case): n이 1 이하일 경우, 팩토리얼 계산을 종료하고 1을 반환합니다.

3. return 1;

   • 팩토리얼 정의에 따라 1! = 1, 0! = 1이므로 반환합니다.

4. return n * Factorial(n - 1);

   • 현재 값 n에 대해 Factorial(n - 1)을 호출하고 그 결과를 곱합니다.
   • 이로 인해 n이 1이 될 때까지 재귀 호출이 이어집니다.

---

실행 과정

• 예를 들어 Factorial(4) 호출 시:
  1. Factorial(4) → 4 * Factorial(3)
  2. Factorial(3) → 3 * Factorial(2)
  3. Factorial(2) → 2 * Factorial(1)
  4. Factorial(1) → 1

출력 결과

• 4! = 4 * 3 * 2 * 1 = 24

---

4. 유클리드 호제법을 활용한 최대공약수(GCD) 계산

코드 예제

int Gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return Gcd(b, a % b);
}

라인별 분석

1. int Gcd(int a, int b)

   • 두 정수 a와 b의 최대공약수(GCD)를 계산합니다.

2. if (b == 0)

   • 종료 조건(Base Case): b가 0일 때, 현재 값 a가 최대공약수입니다.

3. return a;

   • 종료 조건이 충족되면 최대공약수인 a를 반환합니다.

4. return Gcd(b, a % b);

   • 나머지 연산 a % b를 통해 다음 재귀 호출을 수행합니다.
   • 이 과정은 b가 0이 될 때까지 반복됩니다.

---

실행 과정

• 예를 들어 Gcd(48, 18) 호출 시:
  1. Gcd(48, 18) → Gcd(18, 12)
  2. Gcd(18, 12) → Gcd(12, 6)
  3. Gcd(12, 6) → Gcd(6, 0)
  4. Gcd(6, 0) → 종료 조건에 따라 6 반환.

출력 결과

• 최대공약수: 6

---

5. 재귀 함수의 특징과 주의점

특징

1. 문제 분할:
   • 재귀는 복잡한 문제를 작은 단위로 나눠 해결합니다.
2. 스택 사용:
   • 함수 호출 스택을 활용하여 실행 순서를 관리합니다.

---

주의점

1. 종료 조건(Base Case) 누락:

   • 종료 조건이 없으면 무한 호출로 스택 오버플로우가 발생합니다.

2. 스택 오버플로우:

   • 너무 깊은 재귀 호출은 프로그램 종료를 초래합니다.

3. 성능 문제:

   • 반복문보다 호출 오버헤드가 큽니다.

---

6. 재귀 함수의 장단점

장점	단점
간결하고 이해하기 쉬운 코드 작성 가능	종료 조건 없으면 무한 루프 발생
복잡한 문제를 단순화 가능	스택 오버플로우로 프로그램 종료 위험
특정 알고리즘(DFS, A*)에 필수적	반복문보다 실행 속도가 느릴 수 있음

---