자기를 부르는 풀이, 재귀

자기를 다시 불러요

풀이가 자기 자신을 부른다니
좀 이상하게 들리죠.
근데 단순해요.
'풀기(5)'를 풀려면
'풀기(4)'를 풀면 되고,
'풀기(4)'를 풀려면
'풀기(3)'을 풀면 돼요.
같은 풀이를
더 작은 입력으로 다시 부르는 거예요.

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

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

멈추는 바닥

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

바닥 있을 때 vs 없을 때. (있으면 1에서 멈춤 · 없으면 끝없이 내려감)

바닥이 있으면
내려가다 딱 멈춰서,
거기서부터 답을 들고 올라와요.
바닥이 없으면
0, 음수로 끝없이 내려가
영영 답이 안 나와요.
그러니까 재귀를 쓸 땐
바닥부터 정해야 해요.

쌓였다 풀려요

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

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

내려갈 땐 답이 안 보여서
좀 답답할 수 있어요.
근데 바닥을 찍는 순간
거꾸로 술술 풀려요.
쌓인 게 많을수록
올라올 때 합칠 게 많죠.
그래서 너무 깊이 쌓이면
버거워지는데,
그 얘긴 다음에요.

분할정복과 한 몸

지난 강을 떠올려봐요.
큰 문제를 반으로 쪼개
각각 풀고 합쳤죠.
그 '쪼개서 각각 푼다'가
사실은 재귀예요.
풀기(8)이
풀기(4)과 풀기(4)을 부르고,
그 4들이 또
풀기(2)을 부르거든요.

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

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

재귀, 한 줄로

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

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

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