재귀코드로 하노이의 탑 코드를 짜던데 도데체 어떻게 그런 간단한코드가


하노이의 탑의 규칙을 내포할수있지 하고 고민해봤는데



대충이나마 이해하는방법을 생각해봤는데의견나눠봅니다.


제 아이디어는 수학적 귀납법을 써보는겁니다.



n=1,2,3 정도일때는 그림으로 그리기쉬우니, 그림과 코드를 같이보면서 해보고


이렇게 가정을세우는거죠. " H(n) : 함수 hanoi(n)은 하노이탑 게임의 규칙을 만족하면서 원판들을 옮긴다"라고


k>=2인 자연수 k에 대해서


n=1 일때 위에서 확인한대로 H(1)는 참

n=k-1(>=1)에 대해서 H(k-1)가 참이라고 가정해봤을때 H(k)가 참임을 보이면되는데

이건 하노이의탑 코드가 재귀식이라서 증명하기 쉬울것같습니다.


따라서 모든 n에 대해서 hanoi(n)은 하노이의탑 게임의 규칙을 만족하면서 원판을 옮긴다는게 증명되는거죠.