나를 다시 부른다! 재귀
안녕, 나 코딩냥이다냥! 3장에서 반복문을 배웠지? 오늘은 반복의 다른 얼굴을 배운다냥. 함수가 자기 자신을 부르는 거라냥. 처음엔 머리가 어질어질하지만, 익숙해지면 반복문으로는 짜기 힘든 것들이 술술 풀린다냥.
오늘의 학습 목표
- 재귀의 두 부분 — 멈추는 조건과 자기 호출 — 을 나눠 쓴다.
- 문제를 더 작은 같은 문제로 쪼개는 사고방식을 익힌다.
- 재귀가 느려지는 이유와 고치는 법을 안다.
- 재귀로 모든 경우를 만들어내는 방법을 익힌다.
1단계 · 재귀는 두 부분뿐이라냥 (7분)
재귀 함수는 늘 두 조각으로 되어 있다냥. 이것만 기억하면 절반은 끝이라냥.
def countdown(n):
if n == 0: # 1. 멈추는 조건
print("끝")
return
print(n)
countdown(n - 1) # 2. 더 작은 문제로 자기 호출비유로 이해하기 — 러시아 인형
인형을 열면 안에 더 작은 인형이 있다냥. 또 열면 더 작은 인형이 있고. 언젠가 더 안 열리는 가장 작은 인형이 나온다냥. 그게 멈추는 조건이라냥.
멈추는 조건을 빼먹으면 프로그램이 죽는다냥.
파이썬은 재귀가 1000번쯤 쌓이면 RecursionError 를 낸다냥. 무한 반복처럼
멈추지 않는 게 아니라 에러로 터진다냥.
그리고 자기 호출은 반드시 더 작은 문제여야 한다냥. f(n) 안에서 f(n)
을 부르면 영원히 작아지지 않는다냥.
2단계 · 반복문과 뭐가 다르냥 (7분)
카운트다운은 반복문으로도 되는데 왜 재귀를 쓰냥? 솔직히 그건 반복문이 낫다냥. 재귀가 빛나는 건 갈래가 둘 이상일 때라냥.
# 길이 n 인 이진 문자열을 전부 만든다냥
def go(cur):
if len(cur) == n:
print(cur)
return
go(cur + "0") # 0을 붙이는 갈래
go(cur + "1") # 1을 붙이는 갈래위 코드는 자기를 두 번 부른다냥. 0을 붙인 경우와 1을 붙인 경우를 각각 끝까지 따라간다냥.
이걸 반복문으로 짜려면 직접 스택을 만들어야 한다냥. 재귀로는 두 줄이라냥.
갈래가 여러 개로 뻗는 문제 = 재귀 라고 기억하자냥.
n = 3 일 때 어떤 순서로 나오는지 손으로 따라가보자냥.
000, 001, 010, 011, 100, 101, 110, 111
0 을 먼저 부르니 0 으로 시작하는 게 전부 먼저 나온다냥. 부르는 순서를
바꾸면 결과 순서도 바뀐다냥.
3단계 · 하노이 탑 (10분)
재귀의 고전이라냥. 처음 보면 어렵지만, "내가 직접 옮기지 않는다" 고 생각하면 갑자기 쉬워진다냥.
원판 n개를 1번에서 3번으로 옮기고 싶다냥. 이렇게 생각한다냥.
- 위에 있는
n-1개를 2번 기둥으로 옮긴다 (누가 해준다고 치자냥) - 제일 큰 원판 하나를 1번 → 3번 으로 옮긴다 (이건 내가 한다냥)
- 2번에 있는
n-1개를 3번으로 옮긴다 (또 누가 해준다고 치자냥)
"누가 해준다"는 게 바로 자기 호출이라냥. 내가 할 일은 가운데 한 줄 뿐이라냥.
def hanoi(k, start, end, via):
if k == 0:
return
hanoi(k - 1, start, via, end) # 위 k-1개를 via 로
print(start, end) # 큰 거 하나를 옮긴다냥
hanoi(k - 1, via, end, start) # via 의 k-1개를 end 로기둥 세 개의 역할이 매번 바뀐다는 게 헷갈리는 부분이라냥.
첫 번째 호출에서는 end 가 경유지가 되고, 두 번째 호출에서는 start 가
경유지가 된다냥. 인자 순서를 잘못 넘기면 이동 순서가 통째로 틀린다냥.
손으로 n = 2 를 따라가보면 금방 이해된다냥.
4단계 · 재귀가 느려질 때 (12분)
재귀에는 큰 함정이 하나 있다냥. 피보나치를 재귀로 짜보면 바로 만난다냥.
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)깔끔해 보이지만 fib(50) 을 부르면 끝나지 않는다냥.
이유는 같은 값을 몇 번이고 다시 계산하기 때문이라냥.
fib(5)
├ fib(4)
│ ├ fib(3)
│ │ ├ fib(2) ←
│ │ └ fib(1)
│ └ fib(2) ←
└ fib(3)
├ fib(2) ←
└ fib(1)
fib(2) 를 세 번이나 부른다냥. n 이 커지면 이 중복이 폭발한다냥.
fib(50) 은 호출이 수백억 번이라냥.
고치는 법 — 한 번 계산한 건 적어두자냥
memo = {}
def fib(n):
if n < 2:
return n
if n in memo: # 이미 계산했으면 꺼내 쓴다냥
return memo[n]
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]이걸 메모이제이션이라고 한다냥. 5장에서 배운 딕셔너리가 여기서 쓰인다냥.
파이썬에는 이걸 자동으로 해주는 도구도 있다냥.
from functools import lru_cache
@lru_cache(None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)함수 위에 한 줄 붙이면 끝이라냥.
5단계 · 절반씩 줄이는 재귀 (10분)
6장에서 이분 탐색을 배웠지? 재귀에도 같은 아이디어를 쓸 수 있다냥.
a 를 b번 곱하는 걸 훨씬 빠르게 하는 방법이라냥.
2^10 을 구한다고 하자냥. 10번 곱하는 대신 이렇게 한다냥.
지수를 반으로 쪼갠다냥
한 번 쪼갤 때마다 지수가 절반이 된다냥. 그래서 b번이 아니라
약 log b 번이면 끝난다냥.
def power(a, b):
if b == 0:
return 1
half = power(a, b // 2) # 절반을 한 번만 계산한다냥
if b % 2 == 0:
return half * half
else:
return half * half * apower(a, b // 2) 를 변수에 담아 한 번만 부르는 것이 핵심이라냥.
return power(a, b//2) * power(a, b//2) # 이러면 안 된다냥!이렇게 쓰면 같은 걸 두 번 계산해서 결국 b번 곱하는 것과 같아진다냥.
피보나치에서 본 그 함정이라냥.
오늘 배운 내용 정리
먼저 스스로 답해보고, "정답 보기"를 눌러서 맞는지 확인해보자냥!
이제 직접 풀어볼 차례다냥
오늘 문제는 다섯 개라냥. 12번은 재귀로 만들어내기, 34번은 느려지는 걸
막기, 5번은 모든 경우를 살펴보기라냥. 손으로 작은 값을 따라가보는 것이
오늘의 최고 무기라냥. 가보자냥~