[알고리즘] 하노이의 탑_재귀

 

하노이의 탑 점화식은 다음과 같다.

 

f(n) = 1 ( n = 1)

f(n) = f(n-1) + f(n-1) + 1 (n>=2)

 

하노이의 탑은 이렇게 표현 가능하다.

 

그러면 왜 이렇게 되는 걸까?

 

 

 

 

일단 1개일 때는 그냥 3번째로 바로 옴기면 된다.

3개를 옮기는 경우를 생각해보자.

 

 

두개를 2번째 칸으로 옮긴다

+f(2)

 

마지막 1개를3번째 칸으로 옮긴다.

+1

2개를 3번째 칸으로 옮긴다.

+f(2)

 

즉, f(3) = f(2) + 1 + f(2) 

이러한 것은 n=>2일때 모두 적용되는 것이다.

 

따라서 이것을 일반화 해보자면.

 

f(n) = f(n-1) + f(n-1) +1

=2f(n-1) + 1

이 된다.

 

또 재귀적인 방법 말고도 다른 방식으로 하노이의 탑을 표현 할 수 있다.

 

f(n) = 2^n - 1 이다.