파이썬 배우기: 재귀 함수 활용하기

파이썬에서 재귀 함수(Recursive Function)는 자기 자신을 호출하는 함수입니다.
재귀를 활용하면 반복문 없이도 복잡한 문제를 간결하게 해결할 수 있습니다.

이번 글에서는 재귀 함수의 개념, 기본 원리, 활용 예제 등을 자세히 알아보겠습니다.

재귀 함수란?

✅ 자기 자신을 호출하는 함수
✅ 종료 조건(Base Case) 이 반드시 필요
✅ 반복문 없이 재귀 호출을 통해 문제를 해결

📌 기본 구조

def recursive_function():
    print("재귀 함수 호출")
    recursive_function()  # 자기 자신 호출

recursive_function()  # 무한 루프 발생

🔹 위 코드를 실행하면 함수가 계속 호출되어 무한 루프가 발생합니다.
🔹 이를 방지하려면 종료 조건(Base Case)을 설정해야 합니다.

재귀 함수의 종료 조건 (Base Case) 설정하기

재귀 함수는 무한히 호출되면 안 되므로 반드시 종료 조건이 필요합니다.

종료 조건을 추가한 예제

def countdown(n):
    if n <= 0:  # 종료 조건
        print("종료!")
        return
    print(n)
    countdown(n - 1)  # 자기 자신 호출 (n 감소)

countdown(5)

✅ 실행 결과

5
4
3
2
1
종료!

🔹 n <= 0이 되면 더 이상 재귀 호출을 하지 않음 → 무한 루프 방지
🔹 countdown(n - 1)을 호출하면서 n이 점점 감소

재귀 함수의 동작 원리 (스택 구조)

재귀 함수는 함수 호출 스택(Call Stack)을 이용하여 동작합니다.

✅ countdown(3) 실행 과정

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

🔹 함수가 호출될 때마다 스택에 쌓이고
🔹 종료 조건을 만나면 스택에서 순차적으로 제거됨

재귀 함수 활용 예제

팩토리얼(Factorial) 계산
팩토리얼(Factorial) 이란?
n! = n × (n-1) × (n-2) × ... × 1

def factorial(n):
    if n == 1:  # 종료 조건
        return 1
    return n * factorial(n - 1)  # 재귀 호출

print(factorial(5))  # 5! = 5 × 4 × 3 × 2 × 1 = 120

✅ 실행 결과

120

🔹 factorial(5) = 5 × factorial(4)
🔹 factorial(4) = 4 × factorial(3)
🔹 … 반복 후 factorial(1) = 1에서 종료

피보나치수열 (Fibonacci Sequence)

피보나치수열:
0, 1, 1, 2, 3, 5, 8, 13, ...
n번째 피보나치 수: F(n) = F(n-1) + F(n-2)

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)  # 재귀 호출

print(fibonacci(6))  # 8

✅ 실행 결과

8

🔹 fibonacci(6) = fibonacci(5) + fibonacci(4)
🔹 … 계속 재귀 호출하여 값 계산

재귀 호출이 많아지면 성능이 느려질 수 있음!
동일한 값이 반복 계산되므로 “메모이제이션(Memoization)“을 활용하면 성능 개선 가능!

재귀를 이용한 리스트 합 계산

def list_sum(arr):
    if not arr:  # 리스트가 비어 있으면 0 반환 (종료 조건)
        return 0
    return arr[0] + list_sum(arr[1:])  # 첫 번째 요소 + 나머지 요소 합

numbers = [1, 2, 3, 4, 5]
print(list_sum(numbers))  # 15

✅ 실행 결과

15

🔹 list_sum([1, 2, 3, 4, 5]) = 1 + list_sum([2, 3, 4, 5])
🔹 마지막 list_sum([]) = 0에서 종료

재귀를 이용한 문자열 뒤집기

def reverse_string(s):
    if len(s) == 0:  # 종료 조건
        return s
    return s[-1] + reverse_string(s[:-1])  # 마지막 글자 + 나머지 부분 재귀 호출

print(reverse_string("hello"))  # "olleh"

✅ 실행 결과

olleh

🔹 reverse_string("hello") = "o" + reverse_string("hell")
🔹 마지막 reverse_string("")에서 종료

재귀 함수 vs 반복문 (for, while)

재귀 함수 장점

• 코드가 간결
• 복잡한 알고리즘(트리 탐색, DFS 등) 구현이 쉬움

재귀 함수 단점

• 메모리 사용량이 많음 (스택 오버플로우 위험)
• 속도가 느릴 수 있음 (반복문이 더 빠른 경우도 많음)

재귀 함수 최적화 (메모이제이션)

재귀 호출이 많아지면 동일한 계산을 반복 수행하게 되어 비효율적일 수 있습니다.
이를 해결하기 위해 메모이제이션(Memoization, 캐싱) 을 사용합니다.

피보나치수열 (메모이제이션 적용)

memo = {}

def fibonacci(n):
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    elif n == 1:
        return 1
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return memo[n]

print(fibonacci(50))  # 빠르게 계산 가능!

메모이제이션을 적용하면 중복 계산을 방지하여 성능 향상!

마무리 및 요약

✅ 재귀 함수는 자기 자신을 호출하는 함수
✅ 종료 조건(Base Case)을 반드시 설정해야 함
✅ 스택 구조(Call Stack)를 사용하여 동작
✅ 팩토리얼, 피보나치, 문자열 뒤집기, 리스트 합 계산 등에 활용 가능
✅ 반복문보다 성능이 떨어질 수 있음 → 메모이제이션을 활용하면 개선 가능

이제 재귀 함수를 활용해 더 효율적인 알고리즘을 작성해 보세요!

#파이썬 #Python #재귀함수 #알고리즘 #코딩기초 #프로그래밍 #PythonTips #파이썬공부 #개발자 #Python3