base case 와 재귀 케이스: 두 부분 계약

"재귀는 약속 둘이란 걸 보기 전까진 마법이나 광기처럼 느껴져: '이건 바로 답할 수 있는 경우야', 그리고 '다른 모든 경우는, 그쪽으로 줄여갈게.' 둘 다 쥐면 재귀가 안전하고; 하나 놓치면 나선으로 떨어져."

자기 자신을 부르는 함수

재귀는 같은 문제의 더 작은 버전에 자신을 불러 문제를 푸는 함수야. 순환처럼 들리고, 순환일 거야 — 순환을 깨는 조각만 빼면. 모든 정확한 재귀가 정확히 두 부분을 가져:

base case: 더 재귀 없이 즉시 답할 만큼 작은 문제. 하강을 멈추는 바닥.
재귀 케이스: 더 작은 버전을 풀고 (자신을 불러), 그걸로 이 답을 지어 — 늘 base case 쪽으로 움직이며.

팩토리얼이 정석: factorial(0) = 1 (base case), factorial(n) = n × factorial(n−1) (재귀 케이스, n 을 0 쪽으로 줄임). 각 호출이 한 겹 벗겨 base 칠 때까지, 그다음 답이 다시 곱해 올라.

깨지는 두 방법

재귀는 정확히 두 방법으로 실패하고, 둘 다 계약 실패야. 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 + '더 작은 호출이 맞다고 가정, 그 위에 짓기'. 그 가정이 Trees 트랙의 믿음의 도약이야: 재귀 케이스 쓸 때, 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:])   # 첫째 + 나머지의 합 (더 작음)

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 일 때, '발사' 출력하고 return. 재귀 케이스: n 출력하고, n−1 에 재귀. base case 제거 → 음수로 영원히 카운트 → RecursionError. n (n−1 아니라) 에 재귀 → 절대 안 줄어 → 역시 RecursionError. 둘 다 'base 로의 진전' 반쪽 계약을 깨.

자기 자신을 부르는 함수

깨지는 두 방법

재귀는 돌아가는 귀납이야

피파의 고백

Code

External links

Exercise

Progress

댓글 0