18. 파이썬 재귀 함수 (Recursive Functions)

파이썬 재귀 함수에 대해서 알아보자

재귀 함수는 함수가 자기 자신을 호출하는 방식으로 문제를 해결하는 함수이다. 재귀 함수는 복잡한 문제를 단순한 형태로 분할하여 해결할 수 있는 강력한 기법을 제공한다. 

• 기본 조건(Base Case): 재귀 호출을 중단하고 결과를 반환하는 조건.

• 재귀 조건(Recursive Case): 함수가 자기 자신을 호출하여 문제를 더 작은 문제로 분할하는 조건.

1. 재귀 함수의 기본 구조

def 함수이름(매개변수):
    if 기본 조건:
        return 기본값
    else:
        return 함수이름(변환된 매개변수)

2. 재귀 함수의 예제

예제 1: 팩토리얼 계산

팩토리얼은 1부터 주어진 수까지의 모든 정수를 곱한 값이다. 예를 들어, 5의 팩토리얼은 5! = 5 × 4 × 3 × 2 × 1 = 120이다.

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

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

• 기본 조건: n == 0일 때, 1을 반환한다.

• 재귀 조건: n * factorial(n - 1)을 계산하여 함수가 자기 자신을 호출한다.

예제 2: 피보나치 수열 계산

피보나치 수열은 각 항이 그 이전 두 항의 합인 수열이다. 예를 들어, 피보나치 수열의 처음 몇 항은 0, 1, 1, 2, 3, 5, 8, 13, ...이다.

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(6))  # 출력: 8

• 기본 조건: n <= 1일 때, n을 반환한다.

• 재귀 조건: fibonacci(n - 1) + fibonacci(n - 2)를 계산하여 함수가 자기 자신을 두 번 호출한다.

3. 재귀 함수의 장점

• 간결함: 복잡한 문제를 재귀적으로 분할하여 코드가 간결하고 이해하기 쉬워진다.

• 자연스러운 표현: 재귀 함수는 수학적 정의나 문제의 자연스러운 구조를 반영할 수 있다.

4. 재귀 함수의 단점

• 성능: 많은 재귀 호출이 발생할 경우 함수 호출 스택이 커져 메모리 사용이 증가하고 성능이 저하될 수 있다.

• 깊이 제한: 파이썬은 기본적으로 최대 재귀 깊이에 제한이 있으며, 이를 초과하면 RecursionError가 발생한다.

import sys
print(sys.getrecursionlimit())  # 기본 재귀 깊이 제한 출력 (보통 1000)

재귀 깊이 제한을 변경할 수 있지만, 너무 큰 값으로 설정하면 메모리 문제가 발생할 수 있다.

sys.setrecursionlimit(2000)  # 재귀 깊이 제한을 2000으로 설정