Question

如何理解汉诺塔的递归

Answer 1

汉诺塔可以理解为一个移动塔的游戏，把一个n层的塔从一个柱子移动到另一个柱子上

2.这就是汉诺塔递归原型 hannuota（n, A,C）--n层的塔从A柱移动到C柱；每次必须回归到这个原型才算一次递归完成！
<就像1-100的递归累加f(n)=f(n-1)+n； 此时f(n)是递归原型，回归到f(n-1)>

3.中间需要借助一个柱子B，汉诺塔原型写成hunnuota(n,A,B,C)--n层塔从A柱借助B柱移动到C柱，这一步应该能够理解吧；

4.递归都要求有一个出口，也即是控制条件，当n=1时直接把塔从A移动到C即可，这就是出口
<如果n=2则需要移动两次才行，无法一次完成，不能出去>

5.n>1时,这一步是理解汉诺塔递归的关键，必须形成n-1层往C柱移动的形式，分为三步：
a. n层无法一次移动，那么可以理解为先把A上面的n-1层移动到B柱
<hannuota(n-1,A,C,B)>-------
b A柱剩下第n层的塔移动到C，
C 然后形成B柱上的n-1层移动到C柱上--
<hannuota（n-1,B,A,C）此时已经形成了递归的原型 不同的只是中间借助的柱子不同罢了>
递归完成