recursion이란 무엇인가요?

**Recursion(재귀)**은 함수가 같은 문제의 더 작은 버전을 풀기 위해 자기 자신을 호출하는 것입니다. 모든 재귀는 멈추게 하는 **base case(기저 사례)**와 base case를 향해 나아가는 **recursive case(재귀 사례)**가 필요합니다.

개념

문제를 더 작고 동일한 부분 문제로 분해합니다. 각 호출은 **call stack(호출 스택)**에 프레임을 쌓고, 반환은 그것을 꺼냅니다.

예시

def factorial(n):
    if n <= 1:            # base case: 재귀를 멈춤
        return 1
    return n * factorial(n - 1)   # recursive case: 더 작은 문제

factorial(4)             # 4 * 3 * 2 * 1 -> 24

추적

factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24

복잡도

여기서는 O(n) 시간과 O(n) 스택 공간(호출당 프레임 하나)입니다.

함정

• base case 누락 -> 무한 재귀 -> 스택 오버플로.
• 깊은 재귀는 스택을 소진할 수 있으며, 일부 언어는 tail-call optimization을 지원하지 않습니다.
• 겹치는 부분 문제를 재계산하면 지수 시간으로 폭증할 수 있습니다(memoization으로 해결).

왜 중요한가

Recursion은 자연스럽게 자기 유사적인 문제 — 트리, 그래프, 분할 정복 — 를 루프보다 훨씬 깔끔하게 표현합니다.

merge sort, backtracking, dynamic programming 뒤에 있는 사고 모델입니다.

call stack을 이해하면 디버깅과 메모리 추론에도 더 능숙해집니다.