하노이의 탑 - 재귀함수에 대한 생각 2

재귀 함수를 이용한다는 것은 맹목적 믿음이 필요하다. 이전 글에서 재귀 함수를 완전히 이해했나 싶었지만, 하노이의 탑을 만나고 다시 좌절했다.

 재귀함수는 큰 문제를 작은 문제로 나누어서 작은 문제에만 신경을 쓰면 되기 때문에 재귀는 가독성도 좋고, 코드도 짧아지고, 각 단계의 변수 상태 또한 스택 프레임에 저장되기 때문에 너무나 좋다. 어렵게 느껴지는 하노이의 탑을 현 문장의 장점에 맞춰 생각해보려고 한다.

1. 큰 문제를 작은 문제로 나누기

먼저 우리가 해결해야하는 첫번째 목적(문제)는 제일 하단에 있는 것을 목적지로 옮기는 것이다. 그리고 두번째 목적은 최하단 위로 있는 모든 원반(n-1)개를 목적지가 아닌 다른 곳에 두어야한다.

이렇게 부분 문제가 있다. 

2.  원반이 2개있는 경우

여기서 파란색과 노란색원반을 목적지 C로 옮기고 싶다.

먼저 우리가 해결해야하는 문제는 파란색을 C로 옮겨야한다. 그러기 위해서 노란색 원반을 B로 옮겨야한다.

그러니 이걸 정리하면
1. 파란색원반(제일 마지막 원반)을 C이란 목적지로 옮겨야한다.
2. 노란 색원반( 최하단 원반을 제외한 나머지 원반)을 B로 옮겨야한다.

2를 해결해야지 1을 해결할 수 있게 된다.

3. 원반이 3개이 있는 경우

1. 파란색원반(제일 마지막 원반)을 C이란 목적지로 옮겨야한다.
2. 노란 색원반과 주황색 원반을( 최하단 원반을 제외한 나머지 원반)을 B로 옮겨야한다.

이제 코드를 짜보기 위해 생각해보자.

우리는 두가지 문제를 해결해야한다.

1. 최하단  원반을  출발지에서 목적지로 옮긴다.
2. 최하단 원반을 옮기기 위해서 나머지 원반을 출발지에서 경유지(B, 처음의 경우)로 옮겨야한다.
즉 나머지 원반을 출발지로 부터 목적지(경유지)로 옮겨야한다.

결국 1번과 2번은 같은 꼴이다.
왜냐면 출발지로부터 목적지로 원반을 이동시키면 되기 때문이다.

이를 코드로 작성하면 아래처럼 된다.

#include <iostream>
using namespace std;

void hanoi(int n, int from, int by, int to){
	hanoi(n-1, from, to, by);
}

n-1개인 나머지 원반을 출발지로부터 목적지(경유지)로 일동시켜라. 그 다음 문제는 무엇이었는가?

마지막 원반을 출발지에서 목적지로 이동시키는 것이었다.

#include <iostream>
using namespace std;

void hanoi(int n, int from, int by, int to){
	if( n == 1 ) {
          cout << from << ' ' << to << '\n';
          return ;
    }
}

그리고 나머지 n-1개 원반을 다시 C로 이동시켜야한다.

#include <iostream>
using namespace std;

void hanoi(int n, int from, int by, int to){
	if( n == 1 ) {
          cout << from << ' ' << to << '\n';
          return ;
    } else {
    	hanoi(n-1, from, to, by);
        hanoi(n-1, by, from, to);
    }
}

이렇게 작성한다면 n이 1이 되었을 때 밖에 이동 경로를 찍을 수 밖에 없다.
중간 경로를 찍기 위해서 재귀 호출 두 사이에 경로를 찍어줘야 한다. 이때 생각해야하는 것은 주황색 원반이다. 주황색원반이 제일 먼저 움직이기 때문이다. 주황색 원반은 1(from)에서 3(to)로 이동함을 알 수 있다. 이렇게 생각할 수 있는 이유도 재귀문제는 큰문제를 작은 문제로 나눠기 때문이다. 

#include <iostream>
using namespace std;
void hanoi(int n, int from, int by, int to){
    if(n == 1){
        cout << from << " " << to << "\n";
        return;
    } else{
        hanoi(n-1, from, to, by);
        cout << from << " " << to << "\n";
        hanoi(n-1, by, from, to);
    }
}

 

하노이의 탑을 배우는 이유는 재귀 함수를 어떻게 작성할 수 있는지 배우기 위함이다. 그런데 하노이의 탑에 너무 매몰되어 재귀 학습을 잊어버리면 안된다. 또한 점화식을 제대로 이해하고 작성하면 좋겠지만 수학을 잘하지 못하면 쉽지는 않다. 그러니 점화식을 외워서 이 문제를 해결한다면 다시 만났을 때 풀지 못한다. 그러니 무작정 암기하지 말자!