Recursion - 컴퓨터공학 > 알고리즘 | AI Insight Note

재귀(Recursion)는 함수가 자기 자신을 호출해 문제를 해결하는 프로그래밍 기법이다. 분할 정복, 트리 순회, 백트래킹의 핵심 구현 방식이다.

재귀의 두 가지 요소

1. 기저 사례 (Base Case): 재귀를 멈추는 조건
2. 재귀 사례 (Recursive Case): 자기 자신을 호출하는 부분

python

def factorial(n):
    if n <= 1: return 1      # 기저 사례
    return n * factorial(n-1)  # 재귀 사례

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

factorial(3)
  → factorial(2)
    → factorial(1)
      → return 1
    → return 2 * 1 = 2
  → return 3 * 2 = 6

python

# 일반 재귀: 스택 프레임 축적
def factorial(n, acc=1):
    if n <= 1: return acc
    return factorial(n-1, n*acc)  # 꼬리 재귀