재귀 함수(Recursive Function): 반복을 최적화하는 강력한 기법
🔹 재귀 함수란?
1. 재귀 함수(Recursive Function)의 정의
재귀 함수(Recursive Function)란 자기 자신을 호출하는 함수로, 반복적인 문제를 간결하고 효과적으로 해결하는 기법입니다.
✅ 재귀 함수의 주요 특징:
- 기본 조건(Base Case)과 재귀 호출(Recursive Case)로 구성됨
- 문제를 작은 부분 문제로 나누어 해결 (Divide & Conquer, DP)
- 함수 호출 스택(Stack)을 활용하여 실행됨
- 잘못된 구현 시 무한 재귀(Recursion Depth Exceeded) 발생 가능
📌 재귀 함수는 다양한 알고리즘에서 활용되며, 특히 동적 계획법(DP)과 분할 정복(Divide & Conquer)에 유용합니다.
🔹 재귀 함수의 동작 과정
- 기본 조건(Base Case)이 충족되면 재귀 호출 종료
- 재귀 호출(Recursive Case)로 문제를 더 작은 부분으로 나눔
- 스택(Stack)을 사용하여 함수 호출을 관리
✔️ 재귀 함수 예제 (Python):
def recursive_function(n):
if n <= 0:
return 0 # 기본 조건 (Base Case)
print(f"재귀 호출: {n}")
return recursive_function(n - 1) # 재귀 호출
recursive_function(5)📌 기본 조건(Base Case)이 없으면 무한 루프가 발생할 수 있습니다.
🔹 재귀 함수의 주요 활용 사례
1. 팩토리얼 계산(Factorial) - O(n)
✅ n! (n 팩토리얼)을 계산하는 간단한 재귀적 문제
✔️ 팩토리얼 예제 (Python):
def factorial(n):
if n == 0:
return 1 # 기본 조건(Base Case)
return n * factorial(n - 1) # 재귀 호출
print(factorial(5)) # 출력: 120📌 팩토리얼은 반복문으로도 구현할 수 있으나, 재귀를 활용하면 코드가 간결해집니다.
2. 피보나치 수열(Fibonacci Sequence) - O(2^n) (기본)
✅ 재귀를 활용한 피보나치 수열 계산
✔️ 기본 재귀 방식 (비효율적):
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(10)) # 출력: 55📌 이 방식은 중복 계산이 많아 매우 비효율적입니다.
✔️ 메모이제이션(Memoization) 적용 (O(n)):
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(10)) # 출력: 55📌 동적 계획법(DP) 기법을 사용하면 속도가 비약적으로 향상됩니다.
3. 하노이의 탑(Tower of Hanoi) - O(2^n)
✅ 3개의 기둥과 N개의 원반이 있을 때, 최소 이동 횟수를 계산하는 문제
✔️ 하노이의 탑 예제 (Python):
def hanoi(n, source, auxiliary, target):
if n == 1:
print(f"{source} -> {target}")
return
hanoi(n - 1, source, target, auxiliary)
print(f"{source} -> {target}")
hanoi(n - 1, auxiliary, source, target)
hanoi(3, 'A', 'B', 'C')📌 하노이의 탑 문제는 재귀를 이해하는 데 좋은 예제입니다.
🔹 재귀 함수 vs 반복문 비교
| 비교 항목 | 재귀 함수 | 반복문 |
|---|---|---|
| 코드 간결성 | ✅ | ❌ |
| 실행 속도 | ❌ (Stack Overhead) | ✅ (빠름) |
| 메모리 사용 | ❌ (Stack 사용) | ✅ (효율적) |
| 이해도 | ✅ (알고리즘 표현) | ❌ (구현 복잡) |
📌 반복문이 더 효율적이지만, 재귀는 코드의 가독성을 높이는 데 유용합니다.
🔹 재귀 함수의 단점과 해결 방법
✅ 단점:
- 스택 오버플로우(Stack Overflow) 가능성
- 중복 계산으로 인해 성능 저하 가능
✔️ 해결 방법:
- 메모이제이션(Memoization) 활용 (중복 계산 방지)
- 꼬리 재귀(Tail Recursion) 적용 (최적화 가능)
- 반복문으로 변환 (Iterative 방식 활용)
📌 재귀 호출이 깊어지는 경우, 반복문으로 변환하여 성능을 개선할 수 있습니다.
📌 결론
✅ 재귀 함수(Recursive Function)는 자기 자신을 호출하는 방식으로 문제를 해결하는 강력한 기법입니다.
✅ 기본 조건(Base Case)과 재귀 호출(Recursive Case)을 명확히 정의해야 합니다.
✅ 팩토리얼, 피보나치 수열, 하노이의 탑 등 다양한 알고리즘에서 활용됩니다.
✅ 중복 계산이 많을 경우, 메모이제이션을 활용하여 성능을 최적화할 수 있습니다.
✅ 스택 오버플로우를 방지하기 위해 꼬리 재귀 또는 반복문 변환을 고려할 수 있습니다.