[Python] 알고리즘 개념9 - 재귀 함수의 스택 메커니즘

 

 

🚀 1. 재귀 함수란?

**재귀 함수(Recursion)**는 함수가 자기 자신을 호출하는 방식으로 동작하는 함수예요.

 

💡 쉽게 이해하기

• 📞 전화를 걸면 상대방이 다시 나에게 전화를 거는 것과 비슷해요.
• 🏗 문제를 작은 부분으로 나누어 같은 방식으로 해결해요.
• 🛑 하지만 끝없이 호출되면 안 되므로 **기본 종료 조건(Base Case)**이 필요해요!

 

📌 재귀 함수의 기본 구조

def recursive_function(n):
    if n == 0:
        return 0  # 종료 조건(Base Case)
    return n + recursive_function(n - 1)  # 자기 자신 호출

print(recursive_function(5))  # 5 + 4 + 3 + 2 + 1 + 0 = 15

 

➡ 재귀 함수는 계속해서 자기 자신을 호출하며, 기본 종료 조건을 만나면 하나씩 반환되며 종료됩니다.

---

 

 

🚀 2. 스택(Stack)과 재귀 함수

재귀 함수가 실행될 때, 스택(Stack) 구조를 이용해 함수 호출 정보를 저장해요.

 

📌 스택이란?

• 📦 후입선출 (LIFO, Last In First Out) 구조를 따르는 자료구조예요.
• 🛠 먼저 들어간 데이터가 마지막에 나와요. (예: 접시 쌓기 🍽)

 

💡 재귀 호출이 어떻게 스택을 사용하는지 살펴볼까요?

def countdown(n):
    if n == 0:
        print("끝!")
        return
    print(n)
    countdown(n - 1)  # 자기 자신을 호출

countdown(3)

 

➡ 실행 과정 (스택 흐름):

countdown(3) → countdown(2) → countdown(1) → countdown(0)

 

➡ 반환 과정:

countdown(0) 종료 → countdown(1) 종료 → countdown(2) 종료 → countdown(3) 종료

 

📌 함수가 호출될 때마다 스택에 추가되며, 종료되면 스택에서 하나씩 제거됩니다.

---

 

 

🚀 3. 재귀 함수의 문제점 (스택 오버플로우)

 

💡 재귀 함수의 가장 큰 단점은 스택 오버플로우(Stack Overflow)가 발생할 수 있다는 점이에요!

 

📌 스택 오버플로우란?

• 🚨 너무 깊은 재귀 호출로 인해 스택 메모리가 가득 차면서 프로그램이 멈추는 현상!
• 🛠 Python에서는 기본적으로 최대 재귀 깊이(sys.getrecursionlimit())가 1000으로 설정되어 있어요.

 

➡ 해결 방법: 꼬리 재귀(Tail Recursion) 또는 반복문(Iterative)으로 변환

import sys
sys.setrecursionlimit(2000)  # 재귀 한도를 늘리지만, 너무 높이면 위험해요!

---

 

 

🚀 4. 재귀 vs 반복문 (성능 비교)

재귀 함수는 직관적이지만, 반복문보다 메모리와 실행 시간이 더 많이 필요해요.

 

📌 팩토리얼 계산 비교

 

✅ 재귀 방식

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

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

 

✅ 반복문 방식

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

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

 

➡ 일반적으로 반복문 방식이 메모리 사용이 적고 속도가 빠릅니다!

---

 

 

✅ 마무리 정리

• 재귀 함수는 자기 자신을 호출하는 함수로, 기본 종료 조건이 필요합니다.
• 스택(Stack) 구조를 활용하여 함수 호출 정보를 저장하고 관리합니다.
• 스택 오버플로우를 방지하려면 반복문으로 대체하거나 재귀 한도를 조절해야 합니다.
• 반복문이 메모리 사용과 성능 면에서 일반적으로 더 효율적입니다.