PostsSeriesLabsAlgo

기초 개념

재귀

거울 앞에 거울을 두면

맨 안쪽 상자를 열면 무엇이 나올까요? 먼저 예상을 고르세요

예상을 고르면 상자가 열립니다

처음 예상은 달랐습니다. 맨 안쪽에는 구슬만 있었고 더 열 상자는 없었습니다.

구슬 4개를 세려면 상자를 4개 거쳐야 했습니다. 닫을 때마다 안쪽 답에 1을 더해 바깥 답이 정해졌습니다.

상자 1 열기 → 상자 2 열기 → 상자 3 열기 → 상자 4 열기 → 구슬닫을 때 답이 1 → 2 → 3 → 4 로 이어졌습니다.

  • 열 때 — 안쪽으로 한 겹씩. 답은 아직 모른다
  • 맨 안쪽 — 더 열 상자가 없다. 여기서 첫 답(1)이 생긴다
  • 닫을 때 — 안쪽 답에 1 을 더해 바깥 답이 정해진다. 안쪽이 끝나야 바깥을 안다

자기 안에서 같은 일을 다시 하는 방법 = 재귀

거울 앞에 거울을 두면 거울 속에 거울이 끝없이 이어집니다. 상자는 맨 안쪽에서 끝났습니다. 그래서 답이 나왔습니다.

재귀에는 두 가지가 꼭 있다

  • 멈추는 자리 — 구슬만 있는 맨 안쪽 상자. 더 부르지 않고 답을 돌려준다
  • 작아지는 입력 — 열 때마다 남은 상자가 하나씩 줄었다
  • 하나라도 빠지면 — 끝없이 열기만 한다

코드는 상자 열기를 그대로 옮긴 것이다

factorial(4) 는 1 부터 4 까지 곱합니다. 다음을 눌러 한 줄씩 넘기며 층이 쌓이고 걷히는 걸 보세요. 중간에 한 번 물어봅니다.

다음을 눌러 한 줄씩 넘겨 보세요

n = 4

factorial.py
  1. 1def factorial(n):
  2. 2 if n == 1:
  3. 3 return 1
  4. 4 return n * factorial(n - 1)
0 / 12
  • if n == 1 — 멈추는 자리. 여기서만 자기를 부르지 않는다
  • factorial(n - 1) — 한 칸 작아진 입력으로 자기를 부른다. 층이 하나 쌓인다
  • n * … — 안쪽 층이 값을 돌려주면 그제야 곱한다. 층이 걷힌다

자기를 두 번 부르면 나무가 된다

factorial 은 한 줄로 쌓입니다. 이런 문제는 반복문으로 써도 쉽습니다. 호출이 둘로 갈라지면 모습이 달라집니다.

fib(4)fib(3)fib(2)fib(1)fib(0)fib(1)fib(2)fib(1)fib(0)
호출은 모두 9번입니다. 색이 다른 fib(2) 는 같은 계산을 2번 되풀이합니다.
  • 한 줄로 쌓이면 — 반복문으로 바꿔도 쉽다
  • 둘로 갈라지면 — 반복문으로는 어디까지 했는지 직접 적어 두어야 해서 훨씬 어렵다
  • 폴더 안에 폴더 — 안에 같은 것이 든 구조도 재귀로 쓰면 짧아진다

factorial(4) 에서 곱셈은 어떤 순서로 일어날까요?

멈추는 자리를 빼먹으면

  • if n == 1 이 없으면 — n 이 0, −1, −2 … 로 끝없이 내려간다
  • 1000층쯤 쌓이면 — 파이썬이 RecursionError 를 내고 멈춘다. 기본 한도가 1000 이다
  • factorial(0) — 이 코드는 n 이 1 일 때만 멈춘다. 0 에서 시작하면 한도까지 내려가다 터진다
  • sys.setrecursionlimit(10**6) — 코딩테스트에서는 한도를 이렇게 늘려 쓴다. 너무 깊으면 한도에 닿기 전에 메모리가 먼저 터질 수 있다

깊이가 1만, 10만이 될 수 있는 문제는 재귀 대신 반복문으로 바꾸는 쪽이 안전합니다.

문제에서 이 말이 보이면

같은 모양의 더 작은 문제자기를 둘 이상으로 나눈다폴더·트리처럼 안에 같은 것이 든다

다음 장에서는 일단 전부 해 보는 완전탐색을 봅니다.