[Mathematics for Computer Science] Recurrences 재귀

Recurrences 재귀

재귀를 넘어갔다. 여러가지 내용을 보았는데, 사실 올리기가 너무 힘들다. (기호 찾기가 너무 힘들어서... 꼭 그것만은 아닌 것 같고...)
하지만 이번 내용은 꼭 올려놓아야겠다.

The Tower of Hanoi

하노이의탑 문제이다. (위 그림은 교재의 내용을 그대로 가져온 것이다.) 이 문제를 모른다면 구글로 한번 찾아보길 바란다. 일단 3개의 칸을 노가다로 보여주겠다. 그림을 그릴 수는 없는 관계로 내가 보는 교재에서 나오는 그림을 본뜨겠다.

숫자는 각각의 탑과 그 탑의 크기라고 보면 된다. 바로 위에 보이는 그림은 탑 전체가 이동하기 위해 움직여 온 발자취 같은 것이다. 총 7번을 움직였다. 잘 기억하자 3개의 탑이 움직이는데 일.곱.번. 움직였다.

Finding Recurrence

자! 하노이의 탑에서 재귀적인 움직인이 있는지 없는지 찾아봐야 한다. 탑이 n층으로 이루어져 있다 가정하고, 탑이 옆으로 이동할 때 몇번 움직일까? 이것을 T(n) 이라 하자. 일단 3개의 탑이 옆으로 이동하는 것으로 시작해보자( T(3) ). 어떤 규칙이 있는가? 일단 3번이 움직이려면 1,2번이 움직여야 한다. 그리고 3번이 움직이고 또 1,2번이 움직여서 3번 위로 올라탄다. 잠깐! 1,2번은 마치 2층으로 이루어진 탑과 같다.( T(2) ) T(3) = 2 * T(2) + 1 이렇게 된다. 그리고 이것은 T(n) = 2 * T(n-1) + 1 이런 공식을 유추 한다. 이게 맞는 걸까? 한번 T(2)을 예로들어보자. T(2) = 2 * T(1) + 1 = 2 * 1 + 1 탑이 달랑 하나 있을 때( T(1) )는 한 번만 움직이면 될 것이다.

이렇게 하면 끝인가? 아니다. 확인해보자. 위의 공식에 대한 여러가지 확인(?) 아니 증명법이 있는데 그것들은 다음 시간에 보도록 하자. 오늘 여러분이 알아가야 할 것은 이 공식하나.

T(n) = 2T(n-1) + 1