Note

재귀를 처음 배우신다면 맨 아래에 첨부한 링크를 같이 참조하는 것이 좋습니다.

재귀를 배웁니다. 재귀 함수는 자기 자신을 호출하는 함수입니다. 좋습니다.

재귀로 팩토리얼을 구현합니다. 잘 돌아갑니다. factorial(5)는 factorial(4)를 부르고, 이건 다시 factorial(3)을 부르고… factorial(0)을 부르고, 이건 1을 반환하고, factorial(1)이 여기에 1을 곱해서 1을 반환하고… factorial(5)가 여기에 5를 곱해서 120을 반환합니다. 그럴싸합니다.

재귀로 피보나치를 구현합니다. 잘 돌아갑니다. 강좌에 두 갈래로 마구 뻗는 함수 호출 과정이 그림으로 등장합니다. 구체적으로 뭐가 어떤 순서로 호출되는 건지는 안 나와있지만 넘어갑니다.

문제는 하노이 탑입니다. 풀이가 있지만 이게 왜 동작하는지, 이걸 어떻게 생각해 내는 건지는 알 수 없습니다. 원판 n-1개를 1에서 2로 옮긴다고 했지만 함수 호출이 어떻게 일어나서 그렇게 되는지 추적할 수 없습니다. 원판을 일곱 번 옮기는 그림이 있지만 도움이 되지 않습니다. 며칠째 호출 과정을 추적하다가 결국 포기하고 풀이를 암기하기로 합니다.

제 경험이 그랬다는 건 아니지만, 위와 같은 일을 겪는 사례를 심심찮게 찾아볼 수 있습니다.

재귀가 원래 이렇게 이상한 존재일까요? 그렇지 않습니다. 재귀의 본질은 이 복잡한 호출 과정을 따라가는 데서 나오지 않습니다. 오히려 따라가지 않는 데서 나옵니다.

재귀를 푸는 방법

재귀로 문제를 푸는 규칙은 이렇습니다.

1. 입력 크기가 가장 작을 때 (0, 1 등) 문제를 풉니다.
2. 입력 크기가 N보다 작을 때 문제를 풀 수 있다고 가정합니다. 구체적으로 어떻게 풀었는지는 생각하지 않습니다.
3. 이제 입력 크기가 N일 때 문제를 풉니다.

재귀의 장벽을 깨뜨리는 첫걸음은 2번입니다. “구체적으로 어떻게 풀었는지는 생각하지 않습니다.”

사실 생각해 보면 프로그램의 동작 과정을 바닥까지 다 따라갈 필요가 없습니다. 예를 들어 print (printf, cout, …)도 내부적으로 뭔가를 호출할 텐데, 우리는 print를 처음 배울 때 내부를 굳이 뜯어보지 않습니다. print가 뭔가를 출력하는 함수라고 믿고 그냥 씁니다. 재귀도 마찬가지입니다. 단지 내부가 자기 자신이 될 뿐입니다.

팩토리얼

위 규칙으로 팩토리얼을 풀어봅시다. 먼저 N == 0이라면 1을 반환합니다.

이제 입력 크기가 N보다 작을 때 문제를 풀 수 있다고 가정합니다. 즉 factorial(N-1)은 $(N-1)!$을 반환합니다. 구체적으로 factorial(N-1)이 어떻게 동작하는지는 생각하지 않습니다.

이제 $N! = (N-1)! \times N$이고 $(N-1)!$은 factorial(N-1)이니까, factorial(N-1) * N을 반환하면 됩니다.

이를 재귀로 구현했을 때 왜 제대로 동작하는지를 이해하려면, 마찬가지로 입력 크기가 N보다 작을 때 제대로 동작한다고 가정합니다. 이번에도 구체적으로 왜 그런지는 생각하지 않습니다. factorial(5)를 계산하려고 한번에 다섯 단계까지 깊이 들어갈 필요가 없습니다. factorial(4) = 4!임을 이미 아는 상태라고 가정하고 거기서 바로 끝내면 됩니다. 이걸 일일이 풀어 계산하는 건 컴퓨터의 몫입니다.

하노이 탑

우선 하노이 탑을 풀이할 때 “재귀를 사용해 보자“가 먼저 나오면 안 됩니다. 문제에 대해 아직 아무것도 알아낸 게 없는 상태에서는 재귀를 떠올릴 수 없습니다.

하노이 탑을 손으로 풀려고 시도해 보면, 원판이 클수록 그 위에 있을 수 있는 다른 원판이 많아지기 때문에 옮기기 어렵다는 것을 알 수 있습니다. 특히 맨 밑에 있는 N번째 원판은 매우 제한적인 상황에서만 옮길 수 있습니다. 그럼에도 N번째 원판을 어떻게든 기둥 1에서 3으로 옮겨야 합니다.

N번째 원판을 기둥 1에서 3으로 옮길 수 있는 상황은 어떤 상황일까요?

그래서 맨 처음 해야 되는 일은…

그러면 그 문제는 어떻게 풀어야 할까요?

나머지 과정은 비슷합니다. N번째 원판을 1에서 3으로 옮기고, 2에 있었던 “다른 모든 원판“을 전부 3으로 옮깁니다. 이번에도 구체적으로 어떻게 옮기는지는 생각하지 않습니다.

이를 정리하면,

1. 재귀적으로 원판 N-1개짜리 하노이 탑을 풀어서 1에서 2로 옮긴다.
2. N번째 원판을 1에서 3으로 옮긴다.
3. 재귀적으로 원판 N-1개짜리 하노이 탑을 풀어서 2에서 3으로 옮긴다.

가 됩니다. 이제 위 과정을 그대로 코드로 옮기면 끝입니다. (물론 원판이 1개일 때는 따로 처리합시다.) 재귀의 규칙을 잘 따랐기 때문에 올바르게 동작합니다.

그래도 조금 의심된다면 풀이를 검토해 봅시다.

1. 1번 과정이 끝나면 원판 1부터 N-1까지가 기둥 1에서 2로 옮겨집니다. 재귀의 규칙에 따라, 그게 왜 되는지는 생각하지 않습니다. 그냥 됩니다.
2. 그 상태에서는 N번째 원판을 1에서 3으로 옮길 수 있습니다.
3. 3번 과정이 끝나면 원판 1부터 N-1까지가 기둥 2에서 3으로 옮겨집니다. 이번에도 그게 왜 되는지는 생각하지 않습니다.

이게 진짜 돼요?

얼핏 보면 뭔가 사기인 것 같지만, 이 논리가 통하는 이유는 다음과 같습니다.

1. factorial(0) = 1입니다. 재귀 함수에서 이 경우를 따로 처리했을 것입니다.
2. factorial(1) = 1 * factorial(0)입니다. 바로 위에서 factorial(0) = 1임을 이미 파악했습니다. 따라서 factorial(1) = 1 * 1 = 1입니다.
3. factorial(2) = 2 * factorial(1)입니다. 바로 위에서 factorial(1) = 1임을 이미 파악했습니다. 따라서 factorial(2) = 2 * 1 = 2입니다.
4. factorial(3) = 3 * factorial(2)입니다. 바로 위에서 factorial(2) = 2임을 이미 파악했습니다. 따라서 factorial(3) = 3 * 2 = 6입니다.
5. …
6. factorial(N) = N * factorial(N-1)입니다. 바로 위에서 factorial(N-1) = (N-1)!임을 이미 파악했습니다. 따라서 factorial(N) = N * (N-1)! = N!입니다.

하노이 탑도 마찬가지입니다.

1. 원판이 1개일 때 잘 됩니다.
2. 원판이 1개일 때 잘 된다고 가정하면, 재귀의 규칙에 따라 원판이 2개일 때도 잘 됩니다. 원판이 1개일 때 잘 된다는 것을 바로 위에서 파악했습니다. 따라서 원판이 2개일 때도 잘 됩니다.
3. 원판이 2개일 때 잘 된다고 가정하면, 재귀의 규칙에 따라 원판이 3개일 때도 잘 됩니다. 원판이 2개일 때 잘 된다는 것을 바로 위에서 파악했습니다. 따라서 원판이 3개일 때도 잘 됩니다.
4. …

수학적 배경이 있으시다면 사실 이게 수학적 귀납법과 같은 이치임을 눈치채셨을 수도 있겠습니다. 이것이 바로 재귀의 본질입니다.

이처럼 재귀의 규칙을 수학이 정당화해 주기 때문에, 우리는 재귀의 규칙을 따르는 것에만 신경 쓰면 됩니다. 심지어 저 “$P(1)$이 참이고 그래서 $P(2)$가 참이고…“에도 신경 쓸 필요가 없습니다. 컴퓨터와 수학이 알아서 처리해 줄 것입니다.

비슷한 글

• BaaaaaaaarkingDog, 실전 알고리즘 0x0B강 - 재귀
• Eddy, 야, 너두 재귀할 수 있어: 재귀가 풀리는 4단계 접근법
• djm03178, 재귀 함수에 대한 이해