[250106] 재귀함수 정리

재귀함수란?

1. 재귀함수 정의

• 재귀함수는 함수가 자신 스스로를 호출하는 함수를 말한다
• 주로 특정 문제를 작은 단위로 분할하여 반복적으로 처리할 때 사용된다
• 선입후출임

---

2. 재귀함수의 구조

1. 기저 조건(Base Case)
   1. 재귀 호출을 멈추는 조건
2. 재귀 호출(Recursive Call)
   1. 함수가 스스로를 호출하는 부분

---

3. 기본 예제

팩토리얼 계산

• $$n! = n × (n-1) × (n-2) × ∙∙∙ × 1$$

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

# 사용 예시
print(factorial(5))  # 출력: 120 (5 × 4 × 3 × 2 × 1)

---

4. 재귀 호출의 과정

`factorial(5)` 의 호출 흐름:

1. `factorial(5)` >> 5 * `factorial(4)`
2. `factorial(4)` >> 4 * `factorial(3)`
3. `factorial(3)` >> 3 * `factorial(2)`
4. `factorial(2)` >> 2 * `factorial(1)`
5. `factorial(1)` >> `1` (기저 조건 도달)

결과는 `5 * 4 * 3 * 2 * 1 = 120` 이 도출됨

---

5. 재귀함수의 장점과 단점

장점

• 코드가 간결해지고, 반복문보다 직관적인 경우가 많다
• 특정 알고리즘(예: 분할 정복, 트리 순회)에서 필수적이다

단점

• 잘못 작성할 시 무한 루프(=재귀)에 빠질 수 있음
• 함수 호출 스택 사용으로 인해 메모리 효율성이 낮다
• 깊이가 깊어질 경우 스택 오버플로우가 발생할 수 있음
  • 스택 오버플로우란?
    • 정의: 함수 호출이 너무 깊어져 호출 스택(Call stack)의 메모리를 초과할 때 발생하는 오류
    • 원인: 재귀 호출에 기저 조건(Base Case)이 없거나 너무 많은 재귀 호출로 인해 발생함
    • 해결:
      1. 기저 조건을 명확히 설정한다
      2. 반복문으로 전환한다
      3. `sys.setrecursionlimit()` 으로 재귀 깊이를 조정한다(비권장)

---

6. 기타 예제

1. 피보나치 수열

def fibonacci(n):
    if n <= 1:  # 기저 조건
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)  # 재귀 호출

# 사용 예시
print(fibonacci(6))  # 출력: 8 (0, 1, 1, 2, 3, 5, 8)

2. 파일 디렉토리 탐색

import os

def print_files_in_dir(path):
    for item in os.listdir(path):
        full_path = os.path.join(path, item)
        if os.path.isdir(full_path):  # 디렉토리라면 재귀 호출
            print_files_in_dir(full_path)
        else:  # 파일이라면 출력
            print(full_path)

# 사용 예시
print_files_in_dir("/path/to/directory")

---

7. 주의 사항

1. 기저 조건(Base Case)를 반드시 설정해야함
   1. 기저 조건이 없으면 무한 루프가 발생한다
2. 재귀 깊이 제한에 주의해야함
   1. Python 에서는 기본적으로 최대 재귀 깊이가 `1000` 으로 설정돼있음
   2. 필요 시에 `sys.setrecursionlimit()` 으로 변경이 가능함

---

8. 반복문으로의 변환

• 예: 팩토리얼 계산을 반복문으로 변환

def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

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

---

9. 재귀함수와 DP(Dynamic Programming)

• 피보나치 수열 계산에서 재귀는 중복 계산 문제가 발생할 수 있다
  • 이를 개선하기 위해 메모이제이션(Memoization)을 사용함
    • 메모이제이션이란?
      • 정의: 이전에 계산한 결과를 저장하여 중복 계산을 방지하는 기법임
      • 사용: 주로 재귀함수와 함께 사용하여 성능을 최적화한다
      • 방법:
        1. Python 에서 `dict` `functolls.lru_cache` 를 활용함
      • 예제: 피보나치 수열이 있음

def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

print(fibonacci_memo(50))  # 빠르게 결과 반환

---

정리 🧹

1. 적절하게 설계해야 효율성을 극대화할 수 있음
2. 트리 구조, 조합 생성, 탐색 문제에 적합함
3. 기저 조건과 호출 깊이를 명심할 것
4. 반복문이나 메모이제이션 기법을 적절히 활용할 것