9강 / 20강

재귀 — 거울 속의 거울

자기 자신을 부르는 함수, 그리고 그 밑을 받치는 스택

러시아 인형 마트료시카를 열면 안에 똑같이 생긴 작은 인형이 있습니다. 그걸 또 열면 더 작은 인형이. 언젠가 더 이상 열리지 않는 가장 작은 인형이 나오면 끝나죠.

재귀(recursion)는 함수가 자기 자신을 부르는 것입니다. 왜 이런 이상한 짓을 할까요? 큰 문제를 같은 모양의 작은 문제로 줄일 수 있을 때, 코드가 놀랄 만큼 짧아지기 때문입니다.

🛑

멈춤 조건

가장 작은 인형 — 여기서 끝

🔽

줄이기

한 겹 작은 문제로

🔁

자기 호출

같은 함수를 다시

고등학생거울 속의 거울

재귀는 처음에 어지럽고 나중에 아름다운 개념입니다.

함수가 자기 자신을 부른다

왜 이런 걸 하나

문제 자체가 같은 모양으로 작아지는 경우가 많거든요.

문제	작아진 같은 문제
5! 구하기	5 × 4! 구하기
폴더 안 파일 다 세기	하위 폴더에서 같은 일
트리 순회	왼쪽 가지에서 같은 일

"똑같은데 조금 작은" 문제가 나오면 재귀다

비유 — 러시아 인형(마트료시카)

인형을 열면 똑같이 생긴 작은 인형이 나옵니다. 또 열면 또 나오고요.

동작	재귀로
인형을 연다	함수를 부른다
안에 또 인형	자기를 다시 부른다
가장 작은 인형	멈춤 조건

가장 작은 인형이 안 열리는 것이 중요하다 — 안 그러면 무한

재귀 함수의 두 부분

def 팩토리얼(n):
    if n <= 1:            # ① 멈춤 조건
        return 1
    return n * 팩토리얼(n-1)   # ② 자기 호출 (작아진다)

이 둘만 있으면 재귀다 — 멈추는 곳과 작아지는 호출

재귀의 뼈대: 멈춤 조건 + 자기 호출.

Python 브라우저에서 실행

# 5! = 5 × 4 × 3 × 2 × 1
def 팩토리얼(ㄴ):
    if ㄴ <= 1:                  # ① 멈춤 조건 — 가장 작은 인형
        return 1
    return ㄴ * 팩토리얼(ㄴ - 1)  # ② 한 겹 작은 문제로

print(팩토리얼(5))

# 반복문으로 쓰면 이렇습니다 — 길이는 비슷하지만 발상이 다릅니다
곱 = 1
for ㅇ in range(1, 6):
    곱 *= ㅇ
print(곱)

고등학생멈춤 조건이 없으면

note 의 경고 — 가장 흔한 재귀 버그입니다.

멈추지 않으면 스택이 넘친다 — RecursionError

왜 오류가 나나

6강에서 봤죠 — 함수 호출은 스택에 쌓입니다.

호출	스택
f(5)	1개
f(4)	2개
…	계속 쌓인다
멈추지 않으면	넘친다 ⚠

파이썬은 보통 1000단계에서 멈춘다 — 안전장치

멈춤 조건이 있어도 안 되는 경우

def f(n):
    if n == 0:          # 멈춤 조건은 있는데
        return 1
    return f(n - 2)     # ⚠ 홀수면 0을 지나친다

입력	결과
4 → 2 → 0	멈춘다 ✔
5 → 3 → 1 → -1 → …	안 멈춘다 ⚠

멈춤 조건에 반드시 도달하는지 를 확인해야 한다

안전하게 if n <= 0 으로 쓰면 됩니다.

비유 — 계단 내려가기

"1층에 닿으면 멈춘다" 는 규칙이 있습니다. 그런데 두 칸씩 내려가면?

시작	결과
짝수 층	1층에 닿는다
홀수 층	1층을 지나쳐 지하로 ⚠

멈춤 조건은 "닿을 수 있어야" 뜻이 있다

확인하는 습관

멈춤 조건이 있나
호출할 때마다 작아지나
작아지면 반드시 멈춤 조건에 닿나

🎮 콜 스택을 눈으로 보기

재귀 함수를 실행하면 부를 때마다 스택에 한 칸씩 쌓이고, 돌아올 때마다 한 칸씩 걷힙니다. 아래에서 한 걸음씩 눌러 보세요. 6강의 접시 더미가 그대로 나타납니다.

쌓이는 순서와 걷히는 순서를 눈으로 확인합니다.

Python 브라우저에서 실행

# 들여쓰기로 스택의 깊이를 눈에 보이게 해 봅니다
def 팩토리얼(ㄴ, 깊이=0):
    들여 = "│  " * 깊이
    print(f"{들여}┌ 팩토리얼({ㄴ}) 시작")
    if ㄴ <= 1:
        print(f"{들여}└ 1 반환 (멈춤)")
        return 1
    결과 = ㄴ * 팩토리얼(ㄴ - 1, 깊이 + 1)
    print(f"{들여}└ {ㄴ} × … = {결과} 반환")
    return 결과

팩토리얼(4)

고등학생재귀 = 스택

note 의 이 등식이 재귀의 정체를 밝힙니다.

재귀는 스택을 자동으로 써 주는 것이다

직접 스택으로 쓰면

# 재귀
def 합(n):
    if n == 0: return 0
    return n + 합(n-1)

# 스택으로
def 합(n):
    스택 = []
    while n > 0:
        스택.append(n); n -= 1
    결과 = 0
    while 스택:
        결과 += 스택.pop()
    return 결과

하는 일이 같다 — 재귀는 스택을 숨겨 준다

그래서 이런 일이 가능합니다

방식	스택
재귀 DFS	파이썬의 호출 스택
반복 DFS	내가 만든 스택

15강에서 같은 코드임을 직접 보게 된다

그럼 뭘 쓸까

	재귀	반복 + 스택
읽기	짧고 명료	길다
깊이 제한	있다 (1000)	없다
속도	조금 느리다	빠르다

깊이가 얕으면 재귀, 깊을 수 있으면 반복

비유 — 메모하며 심부름

방식	비유
재귀	머릿속에 기억한다 — 편하지만 한계가 있다
스택	공책에 적는다 — 번거롭지만 무제한

기억할 게 적으면 머리로, 많으면 적어 둔다

재귀가 진짜 빛나는 순간 — 하노이 탑

원반 N개를 옮기는 문제입니다. 반복문으로 풀려면 머리가 아프지만, 재귀로 보면 세 줄이에요.

위의 N−1개를 보조 기둥으로 옮긴다 (같은 문제, 한 겹 작게)
가장 큰 원반을 목표 기둥으로 옮긴다
보조 기둥의 N−1개를 목표 기둥으로 옮긴다 (같은 문제, 한 겹 작게)

다섯 줄로 하노이 탑을 풉니다. 원반 수만 바꿔 보세요.

Python 브라우저에서 실행

횟수 = 0
def 하노이(ㄴ, 출발, 목표, 보조):
    global 횟수
    if ㄴ == 0:
        return
    하노이(ㄴ - 1, 출발, 보조, 목표)
    횟수 += 1
    print(f"{횟수:2}. 원반 {ㄴ} : {출발} → {목표}")
    하노이(ㄴ - 1, 보조, 목표, 출발)

하노이(3, "A", "C", "B")
print()
print("원반 3개 →", 횟수, "번")
print("원반 20개면 →", 2**20 - 1, "번  (재귀 코드는 그대로인데!)")

재귀의 함정 — 같은 계산을 몇 번이나

피보나치 수열을 재귀로 쓰면 아름답지만, 끔찍하게 느립니다. 같은 값을 몇 번이고 다시 계산하기 때문이에요. 해결책은 계산한 값을 딕셔너리에 적어 두는 것입니다(5강!).

고등학생재귀로 생각하는 법

재귀를 따라가며 이해하려 하면 어지럽습니다. 다른 방법이 있어요.

믿고 맡긴다 — 작은 문제는 이미 풀렸다고 가정

세 단계로 생각합니다

단계	물음
1	가장 작은 경우는 답이 뭔가
2	한 단계 작은 답이 있다면, 그걸로 답을 만들 수 있나
3	작아지는가

2번에서 어떻게 풀리는지 는 생각하지 않는다

예 — 리스트 뒤집기

빈 리스트를 뒤집으면? 빈 리스트
뒤쪽이 이미 뒤집혔다면? 앞의 하나를 맨 뒤에 붙인다
매번 하나씩 줄어든다 ✔

def 뒤집기(x):
    if not x: return []
    return 뒤집기(x[1:]) + [x[0]]

"뒤쪽이 어떻게 뒤집히는지" 는 안 물어봤다

비유 — 줄 세우기 게임

선생님이 말합니다 — "앞 사람에게 자기 번호를 물어보고, 거기에 1을 더해서 답해라."

사람	하는 일
맨 앞	"1번" (멈춤 조건)
나머지	앞에게 물어보고 +1

각자는 앞사람만 봅니다. 전체 줄이 얼마나 긴지 아무도 모릅니다.

각자가 자기 몫만 하면 전체가 풀린다

그래서 재귀가 아름답다

복잡한 문제를 "내 몫 + 남에게 맡기기" 로 줄입니다. 그리고 그 "남" 이 자기 자신이에요.

10강의 트리에서 이 방식이 진가를 발휘한다

같은 답, 호출 횟수는 수천 배 차이. 숫자를 30, 32로 올려 보세요.

Python 브라우저에서 실행

import time

호출수 = 0
def 피보(ㄴ):
    global 호출수
    호출수 += 1
    if ㄴ < 2:
        return ㄴ
    return 피보(ㄴ-1) + 피보(ㄴ-2)

시작 = time.time()
print("피보(25) =", 피보(25), f"| 함수 호출 {호출수:,}번 | {(time.time()-시작)*1000:.0f} ms")

# 적어 두기(메모이제이션) — 딕셔너리 하나로 해결
메모 = {}
호출수2 = 0
def 피보빠름(ㄴ):
    global 호출수2
    호출수2 += 1
    if ㄴ < 2:
        return ㄴ
    if ㄴ in 메모:
        return 메모[ㄴ]
    메모[ㄴ] = 피보빠름(ㄴ-1) + 피보빠름(ㄴ-2)
    return 메모[ㄴ]

시작 = time.time()
print("피보빠름(25) =", 피보빠름(25), f"| 함수 호출 {호출수2:,}번 | {(time.time()-시작)*1000:.0f} ms")

🤔 확인 문제

재귀 함수에 반드시 있어야 하는 것은?

🤔 확인 문제

재귀 호출이 깊어질수록 무엇이 쌓이나요?

🤔 확인 문제

재귀 피보나치가 느린 이유는?

해설 피보(5)를 구하려고 피보(3)을 두 번, 피보(2)를 세 번… 계산합니다. 계산한 답을 딕셔너리에 적어 두면 호출 횟수가 수천 배 줄어요.