어떻게 자기를 부르는 풀이, 재귀

자기를 다시 부른다

풀이가 자기 자신을 부른다니 좀 이상하게 들린다. 그런데 생각보다 단순하다.
'풀기(5)'를 풀려면 '풀기(4)'를 풀면 되고, '풀기(4)'를 풀려면 '풀기(3)'을 풀면 된다.
같은 풀이를 더 작은 입력으로 다시 부르는 거예요.

같은 상자가 더 작은 입력으로 자기를 다시 불러요. (풀기(5) → 풀기(4) → … → 풀기(1))

상자 안에 똑같은 상자, 그 안에 또 똑같은 상자가 있다. 거울 속 거울과 같다.
달라지는 것은 딱 하나, 입력이 한 칸씩 작아진다는 점이다.
작아지고 또 작아지다 보면 언젠가 바로 풀 수 있는 아주 작은 문제가 돼요.

멈추는 바닥

자기를 계속 부르기만 하면 어떻게 될까? 끝없이 내려간다.
그래서 재귀에는 '여기서 멈춰'라는 바닥이 꼭 있어야 해요.
'입력이 1이 되면 더 부르지 않고 바로 답한다' 같은 약속이다.

바닥이 있을 때 vs 없을 때를 견준다. 있으면 1에서 멈추고, 없으면 끝없이 내려가요.

바닥이 있으면 내려가다 딱 멈추고, 거기서부터 답을 들고 올라온다.
바닥이 없으면 0, 음수로 끝없이 내려가서 영영 답이 나오지 않는다.
그러니 재귀를 쓸 때는 바닥부터 정해야 해요.

쌓였다가 풀린다

재귀가 답을 만드는 모습은 두 걸음으로 나뉜다.
내려갈 때는 답을 잠시 미뤄 두고 자기를 계속 부르며 쌓는다.
바닥에 닿으면 이번에는 거꾸로 올라오면서 쌓아 둔 것을 하나씩 합쳐 답을 완성해요.

내려가며 쌓고, 바닥부터 거꾸로 합친다. (곱(4) = 4x3x2x1 = 24)

내려가는 동안에는 답이 보이지 않아 조금 답답할 수 있다.
그런데 바닥을 찍는 순간부터 거꾸로 술술 풀린다. 쌓인 것이 많을수록 올라올 때 합칠 것도 많다.
그래서 너무 깊이 쌓이면 컴퓨터도 버거워한다는 점은 기억해 둘 만해요.

분할 정복과 한 몸

지난 레슨을 떠올려 보자. 큰 문제를 반으로 쪼개 각각 풀고 합쳤다.
그 '쪼개서 각각 푼다'가 사실은 재귀다.
풀기(8)은 풀기(4)와 풀기(4)를 부르고, 각 풀기(4)는 다시 풀기(2)를 두 번씩 불러요.

쪼개기를 재귀 호출로 바꿔 본다. (풀기(8) → 풀기(4)·풀기(4) → 풀기(2)×4)

그래서 분할 정복과 재귀는 따로가 아니라 한 몸이다. 쪼개는 것 = 자기를 다시 부르는 것.
조각이 더 못 쪼갤 만큼 작아지면 그것이 바닥이고, 작은 답들이 위로 합쳐지는 것이 쌓였다가 풀리는 과정이다.
앞에서 본 것이 모두 여기에 모여요.

재귀, 한 줄로

재귀는 세 기둥으로 선다. 자기를 더 작은 입력으로 부르고, 멈추는 바닥이 있고, 쌓였다가 거꾸로 풀린다.
이 셋만 갖추면 복잡해 보이는 문제도 '나보다 작은 나'에게 슬쩍 떠넘겨 풀 수 있어요.

세 기둥을 차례로 눌러 정리해요. (자기를 부름 → 멈추는 바닥 → 쌓였다 풀림)

다만 조심할 것이 하나 있다. 쪼개다 보면 똑같은 작은 문제를 여러 번 거듭 풀 때가 있다.
같은 답을 자꾸 다시 구하면 시간이 아깝다.
한 번 푼 답을 적어 두었다가 다시 쓰는 꾀가 있는데, 그것이 다음 이야기예요.