我意思说hanoi tower的recursion不是重点,induction是重点,而你依然在和我讨论recursion的问题,我给一下我大一时候做hanoi tower的时候的证明(凭记忆再写一下):
假设H(n) n其中n是蝶的过程,则显然 H(1)= 1, 只要移动1步即可。
那么显然 H(k+1)= 2*H(k)+1 , 因为显然(k+1)th的碟子必然要再上面k个碟子移走后,才能把(k+1)th移到第三柱,然后还有通过k个碟子的转移过程才能完成,即,2次k个碟子转移+(k+1)th底碟的转移 ,这个是Hainoi Recursion的定义式,好了,我的意思是recursion定义式不是重点,重点在于induction部分。
Hanoi的问题关键是要证明 2^n-1这个移蝶步骤,证明如下:
当n=1时,显然只要一步就可以完成,所以H(1)=1, 符合2^1-1=1的这个式子
假设当n=k时 H(k)=2^k-1成立
证明n=k+1时 H(k+1)是否还是成立?
H(k+1) 根据recursion定义则可以知道 H(k+1)=2*H(k)+1
=2*(2^k-1)+1 (根据induction 的kth假设)
=2^(k+1)-1
则显然2^n-1这个式子是成立的,并且是Hanoi tower的非递归解。
大部分recursion的问题,在数学上必须抛弃recursion定义,采用“线性”式子表达才是其本质。
比如BST(binary search tree)的复杂度问题,复杂度定义都是recursion,但结论都是 类似于 n Log n的非recursiond的"线性"解,这是我的上贴的意思。