자기를 부르는 함수, 재귀

자기를 부르는 함수

9강에서 함수는 일을 묶어 이름 붙인 거였어요.
그 함수 안에서 다른 함수를 부를 수도 있었죠.
재귀는 거기서 한 발 더 나가요.
함수가 자기 자신을 다시 불러요.
거울 안의 거울처럼, 똑같은 게 한 겹 더 생겨요.

눌러 보세요. 누를 때마다 안에 똑같은 틀이 한 겹씩 더 생겨요.

신기하지만 살짝 무섭기도 해요.
이렇게 계속 자기를 부르면
영원히 안 멈추는 거 아닐까요?
맞아요. 그래서 재귀엔 꼭 필요한 게 하나 있어요.

멈출 곳이 있어야 해요

거울 두 개는 정말 끝없이 들어가지만,
컴퓨터는 '영원히'를 못 해요.
그래서 규칙을 하나 정해요.
'조각이 충분히 작아지면, 거기서 멈춰라.'
이 멈춤 규칙이 없으면 영원히 돌다 무너져요.

멈춤 규칙을 켜면 3, 2, 1에서 딱 서요. 끄면 끝없이 내려가다 무너져요.

이 멈추는 자리를 '바닥'이라고 생각하면 쉬워요.
바닥에 닿기 전까진 자기를 계속 부르고,
바닥에 닿으면 더는 안 불러요.
그럼 이제 어떻게 쪼개느냐가 핵심이에요.

같은 문제의 더 작은 판

재귀의 진짜 비결은 이거예요.
큰 문제를 '한 걸음 + 똑같은데 더 작은 문제'로 보는 거죠.
계단 전체 = 한 칸 + 나머지 계단.
'나머지 계단'도 똑같은 문제, 한 칸 더 작을 뿐이에요.
작아지고 작아지다 0칸에 닿으면 끝.

한 칸씩 떼어 내 보세요. 남은 계단은 매번 '똑같은데 더 작은' 문제예요.

어렵던 문제가 갑자기 쉬워져요.
전부를 한 번에 풀 필요가 없어요.
'한 칸'만 처리하고, 나머지는 똑같은 함수한테 다시 맡기면 되니까요.
그런데 맡긴 일은 어떻게 돌아올까요?

갔다가 다시 돌아와요

재귀는 두 방향으로 움직여요.
먼저 바닥까지 쭉 내려가요(자기를 부르고, 또 부르고).
바닥에 닿으면, 이제 거꾸로 올라오면서
각자 자기 몫을 더해요.
접시를 쌓았다가 위에서부터 다시 치우는 것과 똑같아요.

한 단계씩 눌러 보세요. 1+2+3을 바닥까지 내려갔다가, 올라오며 6으로 모아요.

이 '내려갔다 올라오기'가 재귀의 심장이에요.
내려갈 땐 문제를 쪼개고,
올라올 땐 답을 합치죠.
쌓인 일들이 바닥에서부터 차례로 풀려요.

반복의 형제, 그리고 그 너머

재귀와 반복(7강)은 형제예요.
둘 다 '같은 일을 여러 번' 하지만,
반복은 옆으로 죽 늘어놓고,
재귀는 안으로 한 겹씩 파고들어요.
폴더 안의 폴더처럼, 가지에서 또 가지가 나는 일엔 재귀가 딱이에요.

한 번 누르면 가지가 또 갈라져요. 같은 규칙이 스스로 나무를 그려요.

묶어서 이름 붙인 함수가(9강),
이제 자기 자신까지 부를 수 있게 됐어요.
작게 쪼개고, 바닥에서 멈추고, 다시 모으기.
이 한 가지 생각이 폴더, 댓글의 댓글, 미로 찾기까지 풀어내요.
다음엔 여러 값을 짝지어 담는 법으로 가요.