어떻게 자기를 부르는 함수, 재귀

자기를 부르는 함수

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

한 겹 더를 누를 때마다 안쪽에 똑같은 틀이 한 겹씩 생긴다.

신기하지만 조금 무섭기도 하다.
이렇게 계속 자기를 부르면 영원히 멈추지 않는 것 아닐까?
맞다. 그래서 재귀에는 꼭 필요한 것이 하나 있어요.

멈출 곳이 있어야 한다

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

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

멈추는 자리를 '바닥'이라고 생각하면 쉽다.
바닥에 닿기 전까지는 자기를 계속 부르고, 바닥에 닿으면 더는 부르지 않는다.
그러면 이제 문제를 어떻게 쪼개느냐가 핵심이에요.

같은 문제의 더 작은 판

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

한 칸 떼기를 누를 때마다 계단이 한 칸씩 준다. 남은 계단은 매번 '똑같지만 더 작은' 문제다.

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

갔다가 다시 돌아온다

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

다음 단계를 누르면 1+2+3을 바닥까지 내려갔다가, 올라오며 6으로 모은다.

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

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

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

누를 때마다 가지가 또 갈라진다. 같은 규칙이 스스로 나무를 그린다.

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