[Python] 재귀 함수(Recursive Function)

파이썬

재귀 함수

---

재귀 함수(Recursive Function)는 함수가 자신을 직접 또는 간접적으로 호출하는 함수를 의미한다. 재귀 함수는 일반적인 함수와 유사하게 동작하지만, 자신을 호출하여 같은 작업을 반복하는 데 사용된다. 재귀 함수는 주로 반복적인 작업을 해결하기 위해 사용되며, 특히 작업이 동일한 패턴으로 반복되는 경우 유용하다. 재귀 함수의 주요 특징은 다음과 같다.
 

1. 자기 호출(Self-Call) - 재귀 함수는 자신을 호출한다. 이것이 재귀 함수의 핵심 특징이며, 자기 자신을 호출함으로써 동일한 작업을 반복 수행한다.
2. 종료 조건(Base Case) - 재귀 함수는 종료 조건을 가져야 한다. 종료 조건은 함수가 자신을 계속 호출하는 것을 멈추게 하는 조건이다. 종료 조건이 없으면 함수 호출이 무한히 반복될 수 있다.
3. 작은 문제로 분할 - 재귀 함수는 큰 문제를 작은 하위 문제로 분할하며, 이 하위 문제를 해결하기 위해 자신을 호출한다. 작은 하위 문제들은 종료 조건에 수렴하게 된다.
4. 메모리 스택 사용 - 재귀 함수 호출은 메모리 스택을 사용한다. 각 함수 호출은 스택에 쌓이고, 종료 조건에서 스택에서 제거된다.

재귀 함수의 대표적인 예제로는 팩토리얼 계산, 피보나치수열 계산, 이진트리 순회 등이 있다. 예를 들어, 피보나치수열의 n번째 항을 재귀 함수를 사용하여 계산하면 다음과 같이 표현할 수 있다.
 

재귀함수 - 피보나치수열

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

fibonacci(n)은 fibonacci(n - 1) 및 fibonacci(n - 2)를 호출하여 자신을 호출한다. 종료 조건은 n이 0 또는 1일 때, 즉, n이 작아져서 더 이상 재귀 호출이 필요하지 않을 때이다.

result = fibonacci(10)
print(result) # 출력 : 55

 
 
다음은 재귀 함수의 다른 예제로 팩토리얼(Factorial) 계산을 해보자. 팩토리얼은 양의 정수 n에 대해 n!로 표현되며, n! 는 1부터 n까지의 모든 양의 정수를 곱한 값이다.
 

재귀함수 - 팩토리얼

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

n이 0인 경우 1을 반환하고, 그렇지 않은 경우 n과 (n - 1)의 팩토리얼 값을 곱한 결과를 반환한다.
 

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

n이 5인 경우 팩토리얼 값은 120이다.(5 x 4 x 3 x 2 x 1 = 120).
 
 
읽어주셔서 감사합니다.