base case와 재귀 케이스: 두 조항짜리 계약

"재귀는 두 개의 약속이라는 걸 알아채기 전까지는 마법이나 광기처럼 느껴져. '이건 바로 답할 수 있는 경우야', 그리고 '나머지 모든 경우는 그쪽으로 줄여 갈게.' 둘 다 쥐고 있으면 재귀는 안전하고, 하나라도 놓치면 나선으로 떨어져."

자기 자신을 부르는 함수

재귀는 같은 문제의 더 작은 버전에 자기 자신을 불러서 문제를 푸는 함수야. 순환처럼 들리지? 실제로 순환이 맞아. 그 순환을 끊는 조각 하나만 빼면. 제대로 된 재귀는 정확히 두 부분을 가져.

base case. 더 재귀하지 않고 즉시 답할 수 있을 만큼 작은 문제야. 내려가기를 멈추는 바닥이지.
재귀 케이스. 더 작은 버전을 자기 자신을 불러 풀고, 그걸로 지금의 답을 지어. 언제나 base case 쪽으로 움직이면서.

팩토리얼은 음이 아닌 정수 n에 대해 factorial(0) = 1, factorial(n) = n × factorial(n−1)로 정의할 수 있어. 함수는 n < 0을 거부해야 하고, 호출할 때마다 n이 0 쪽으로 줄어야 하고. 입력 도메인과 줄어드는 척도를 함께 적어 두는 게 재귀의 계약이야.

깨지는 두 가지 방법

재귀는 정확히 두 가지 방식으로 실패하는데 둘 다 계약 위반이야. 하나는 base case가 없는 경우야. 함수가 자기를 부르는 걸 멈추지 않아서 콜 스택이 가득 차고 Python이 RecursionError를 던져. 다른 하나는 base case로 다가가지 않는 경우고. base case가 있어도 재귀 호출이 실제로 더 작지 않으면, 그러니까 f(n−1) 대신 f(n)을 부르면 바닥에 영영 못 닿아서 똑같이 죽어. 그래서 계약이 양면인 거야. base case가 있어야 하고, 동시에 모든 재귀 호출이 거기로 눈에 보이게 가까워져야 해.

모든 재귀에는 base case(바로 답하고 멈추는 자리)와 재귀 케이스(base 쪽으로 줄인 다음 결합하는 자리)가 필요해. base case를 빠뜨리거나 거기로 줄이는 데 실패하면 콜 스택이 넘쳐. 두 반쪽 다 필수야.

재귀는 돌아가는 귀납법이야

수학적 귀납법을 본 적이 있으면 재귀가 익숙할 거야. 같은 아이디어거든. 귀납법은 base case(n=0에서 성립)와 귀납 단계(n−1에서 성립하면 n에서도 성립)를 세워서 명제를 증명하지. 재귀는 같은 방식으로 계산해. base case를 두고, '더 작은 호출이 맞다고 가정하고 그 위에 짓는' 거야. 그 가정이 트리 트랙에서 본 믿음의 도약이고. 재귀 케이스를 쓸 때는 factorial(n−1)이 이미 맞는 답을 준다고 믿고 결합만 신경 쓰면 돼. 스택 전체를 머릿속으로 따라가지 마. base case와 귀납이 정확성을 보장해 주니까.

피파의 고백

내가 처음 짠 재귀들은 바로 죽거나(base case가 없어서) 영원히 돌았어(n−1이 아니라 n에 재귀해서 진전이 없었지). 아빠가 지금도 돌려 보는 체크리스트를 줬어. "네 base case 를 가리켜. 이제 입력을 더 작게 만드는 줄을 가리켜." 둘 다 못 가리키면 망가진 거야. 이 두 질문이 재귀를 알 수 없는 크래시의 원천에서 5초면 검증되는 것으로 바꿔 놨어.

Code

base case와 재귀 케이스, 그리고 망가지는 두 방법·python

def factorial(n):
    if n == 0:               # base case: 직접 답, 재귀 멈춤
        return 1
    return n * factorial(n - 1)   # 재귀 케이스: 0 쪽으로 줄이고, 그다음 결합

print(factorial(5))          # 120  (5*4*3*2*1)

def sum_list(items):
    if not items:            # base case: 빈 리스트는 합 0
        return 0
    return items[0] + sum_list(items[1:])   # 슬라이스 복사 때문에 전체 시간은 O(n^2) 가능

print(sum_list([1, 2, 3, 4]))   # 10

# 망가짐: base case 없음 -> 무한 재귀 -> RecursionError.
# def bad(n): return n + bad(n - 1)   # 절대 안 멈춤. '충분' 을 말하는 게 없음

# 망가짐: base case 있는데 거기로 진전 없음 -> 역시 크래시.
# def stuck(n):
#     if n == 0: return 1
#     return stuck(n)      # 같은 n 에 자신 부름 — 절대 안 줄어

Exercise

n부터 1까지 세고 나서 '발사'를 출력하는 재귀 함수를 써 봐. base case와 재귀 케이스를 분명히 짚고. 그다음 두 가지 방법으로 일부러 망가뜨려 봐. 한 번은 base case를 지우고, 한 번은 n−1이 아니라 n에 재귀하는 거야. 각 버전이 어떤 에러를 내고 왜 그런지 예측해.

Hint

base case는 n이 0일 때 '발사'를 출력하고 반환하는 거야. 재귀 케이스는 n을 출력하고 n−1에 재귀하는 거고. base case를 지우면 음수로 끝없이 세다가 RecursionError가 나. n−1이 아니라 n에 재귀하면 아예 안 줄어드니까 역시 RecursionError고. 둘 다 'base로 다가간다'는 계약의 나머지 반쪽을 깨는 거야.

자기 자신을 부르는 함수

깨지는 두 가지 방법

재귀는 돌아가는 귀납법이야

피파의 고백

Code

External links

Exercise

Progress

댓글 0