4-6. 재귀 함수 이해하기

안녕하세요! 지난 시간에는 파이썬 변수의 유효 범위인 지역변수와 전역변수, 그리고 global 키워드의 사용법과 주의할 점에 대해 알아보았습니다. 이제 변수가 코드의 어디까지 영향을 미 미치는지 이해하셨을 거예요.

이번 시간에는 함수와 관련된 조금 더 고급스러운 개념인 **재귀 함수(Recursive Function)**에 대해 알아보겠습니다. 재귀 함수는 함수 자기 자신을 호출하는 함수를 의미합니다. 처음 들으면 어렵게 느껴질 수 있지만, 특정 종류의 문제들을 매우 우아하고 간결하게 해결할 수 있게 해주는 강력한 기법입니다.

마치 큰 문제를 해결하기 위해 같은 형태의 더 작은 문제를 계속해서 풀어 나가는 것과 같습니다. 그럼, 재귀 함수는 어떻게 작동하는지 함께 살펴볼까요?

---

Part 1: 재귀 함수(Recursive Function)란 무엇인가?

재귀 함수는 함수가 실행되는 도중에 자기 자신을 다시 호출하는 함수입니다. 이 과정을 반복하다가 특정 조건이 되면 더 이상 자기 자신을 호출하지 않고 종료됩니다.

1. 재귀 함수의 두 가지 핵심 요소

재귀 함수가 올바르게 동작하고 무한히 반복되지 않으려면, 반드시 두 가지 중요한 요소가 포함되어야 합니다.

• 기본 사례 (Base Case):
  • 재귀 호출을 멈추는 조건입니다. 이 조건이 충족되면 함수는 더 이상 자기 자신을 호출하지 않고, 결과를 반환하며 재귀 호출의 연속을 끝냅니다.
  • 기본 사례가 없으면 무한 재귀에 빠져 프로그램이 종료되지 않거나, RecursionError (재귀 깊이 초과 오류)가 발생합니다.
• 재귀 단계 (Recursive Step):
  • 함수 자기 자신을 다시 호출하는 부분입니다. 이때, 다음 호출의 입력은 현재 문제보다 더 작아진(단순화된) 형태여야 합니다. 이 작은 문제들이 결국 기본 사례에 도달할 수 있도록 해야 합니다.

---

Part 2: 재귀 함수 예제 1: 팩토리얼(Factorial) 계산

팩토리얼(n)은 1부터 n까지의 모든 양의 정수를 곱한 값입니다. (예: 5=5times4times3times2times1=120)

이 팩토리얼은 재귀 함수의 대표적인 예시입니다.

• 기본 사례: 0=1 또는 1=1 (가장 작은 문제).
• 재귀 단계: n=ntimes(n−1) (더 작은 팩토리얼 문제로 변환).

예시: 팩토리얼 재귀 함수

Python

 

# 파일 이름: factorial_recursion.py

def factorial(n):
    # 1. 기본 사례 (Base Case): 재귀 호출을 멈추는 조건
    if n == 0 or n == 1:
        print(f"팩토리얼({n}): 기본 사례, 결과 1 반환")
        return 1
    # 2. 재귀 단계 (Recursive Step): 함수 자기 자신을 호출
    else:
        print(f"팩토리얼({n}): {n} * 팩토리얼({n-1}) 호출")
        # n * (n-1)의 팩토리얼을 계산한 결과를 반환
        result = n * factorial(n - 1)
        print(f"팩토리얼({n}) 계산 완료, 결과: {result}")
        return result

print("--- 팩토리얼 계산 시작 (5!) ---")
result_5_factorial = factorial(5)
print(f"최종 5! 결과: {result_5_factorial}")

print("\n--- 팩토리얼 계산 시작 (3!) ---")
result_3_factorial = factorial(3)
print(f"최종 3! 결과: {result_3_factorial}")

print("\n--- 팩토리얼 계산 시작 (0!) ---")
result_0_factorial = factorial(0)
print(f"최종 0! 결과: {result_0_factorial}")

• factorial(5)를 호출하면, 5 * factorial(4)가 되고, 다시 4 * factorial(3), 3 * factorial(2), 2 * factorial(1)이 됩니다.
• factorial(1)에서 n == 1 조건이 True가 되어 1을 반환합니다.
• 이후 2 * 1, 3 * 2, 4 * 6, 5 * 24 순서로 계산이 역으로 진행되어 최종 결과인 120이 반환됩니다.

---

 

 

[VS Code 터미널 출력]

 

---

Part 3: 재귀 함수 예제 2: 피보나치 수열(Fibonacci Sequence)

피보나치 수열은 첫 두 숫자가 0과 1이고, 이후의 모든 숫자는 앞의 두 숫자를 더한 값으로 이루어지는 수열입니다. (예: 0, 1, 1, 2, 3, 5, 8, 13, ...)

• 기본 사례:
  • F(0)=0
  • F(1)=1
• 재귀 단계: F(n)=F(n−1)+F(n−2) (두 개의 더 작은 피보나치 문제로 변환).

예시: 피보나치 수열 재귀 함수

Python

 

# 파일 이름: fibonacci_recursion.py

def fibonacci(n):
    # 1. 기본 사례 (Base Case)
    if n <= 1: # n이 0 또는 1일 때
        print(f"피보나치({n}): 기본 사례, 결과 {n} 반환")
        return n
    # 2. 재귀 단계 (Recursive Step)
    else:
        print(f"피보나치({n}): 피보나치({n-1}) + 피보나치({n-2}) 호출")
        # (n-1)번째 피보나치 수와 (n-2)번째 피보나치 수를 더함
        result = fibonacci(n - 1) + fibonacci(n - 2)
        print(f"피보나치({n}) 계산 완료, 결과: {result}")
        return result

print("--- 피보나치 수열 계산 시작 (fibonacci(5)) ---")
result_fib_5 = fibonacci(5)
print(f"최종 fibonacci(5) 결과: {result_fib_5}")

print("\n--- 피보나치 수열 계산 시작 (fibonacci(3)) ---")
result_fib_3 = fibonacci(3)
print(f"최종 fibonacci(3) 결과: {result_fib_3}")

• fibonacci(5)를 호출하면, fibonacci(4) + fibonacci(3)으로 분리되고, 각 부분이 다시 더 작은 문제로 분리되는 과정을 거칩니다.
• 이 과정에서 fibonacci(0)과 fibonacci(1)이라는 기본 사례에 도달하면 재귀가 멈추고 값이 반환됩니다.

---

 

[VS Code 터미널 출력]

(참고: 피보나치 수열 재귀 함수는 같은 계산을 여러 번 반복하므로, 효율성 측면에서는 반복문이나 다른 최적화 기법이 더 좋을 때가 많습니다. 여기서는 재귀의 개념을 이해하는 데 중점을 둡니다.)

---

Part 4: 재귀 함수 사용 시 주의할 점

• 기본 사례 필수: 기본 사례가 없으면 재귀 함수는 무한히 자기 자신을 호출하다가 RecursionError: maximum recursion depth exceeded 오류를 발생시키며 중단됩니다. 파이썬은 기본적으로 재귀 호출 깊이를 1000회 정도로 제한합니다.
  • [참고]: 이 오류가 발생하면, 코드를 잘못 짰거나 (기본 사례 누락/오류) 재귀 호출이 너무 깊어지는 문제이므로 다른 해결 방법을 고려해야 합니다.
• 성능 문제: 일부 재귀 함수(특히 피보나치 수열처럼 같은 계산을 여러 번 반복하는 경우)는 반복문으로 구현하는 것보다 훨씬 비효율적일 수 있습니다. 함수 호출에 오버헤드가 발생하고, 스택 메모리를 많이 사용하기 때문입니다.
• 가독성: 어떤 문제에서는 재귀가 코드를 더 간결하고 우아하게 만들지만, 어떤 경우에는 오히려 이해하기 어려워질 수 있습니다.

언제 재귀 함수를 사용하는 것이 좋을까?

• 문제가 재귀적으로 정의될 수 있을 때 (예: 팩토리얼, 피보나치, 이진 트리 순회 등).
• 코드를 더 간결하고 직관적으로 만들 수 있을 때.
• 반복문으로 구현하기 복잡하거나 비효율적인 특정 알고리즘 (예: 병합 정렬, 퀵 정렬).

---

마무리하며

이번 시간에는 파이썬에서 함수 자기 자신을 호출하는 **재귀 함수(Recursive Function)**에 대해 알아보았습니다. 재귀 함수는 **기본 사례(Base Case)**와 **재귀 단계(Recursive Step)**라는 두 가지 핵심 요소를 통해 문제를 더 작은 문제로 분해하여 해결합니다.

재귀는 처음에는 이해하기 어려울 수 있지만, 특정 문제 유형을 해결하는 데 매우 강력하고 우아한 방법이 될 수 있습니다. 기본 사례를 명확히 설정하고, 재귀 호출이 기본 사례로 수렴하도록 만드는 것이 중요합니다.

이로써 함수(Function) 챕터의 포스팅이 모두 마무리됩니다. 다음 챕터부터는 파일에서 데이터를 읽고 쓰는 **파일 입출력(File I/O)**과 프로그램 실행 중 발생하는 오류를 처리하는 **예외 처리(Exception Handling)**에 대해 자세히 알아보겠습니다.

---

궁금한 점이 있다면 언제든지 질문해주세요! 다음 포스팅에서 만나요!