Question

如何理解汉诺塔递归

Answer 1

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）此时已经形成了递归的原型 不同的只是中间借助的柱子不同罢了>

递归完成

Answer 2

递归程序的运行过程对初学者来说总是很难理解的，主要是对子程序的调用和返回以及对局部变量理解不透所致。递归定义为子程序调用它自身，这种说法也导致理解困难。本质上是每一次调用产生一套新的局部变量，运行的代码行相同，处理的数据（变量）不同。你不要把MoveTower子程序对MoveTower子程序的调用看做对自身的调用，而是看做对另一个子程序的调用（可把MoveTower写很多遍，每次调用是用另一个），用手工分析每一次调用局部变量的变化就清楚了。

Answer 3

递归就是一层套一层，函数自己调用自己，直到出现限制条件为止。函数自己调用自己，可以理解为sum = sum + M；给这个加一个循环 是不是就可以求出总和了；意思是一样的自己调自己，汉诺塔这个比较深，你可以用递归的方式去求所有数字的和，多谢几遍你自然就会了

Answer 4

就是每次把所有的盘子当成2个盘子看，最下面一个盘子看成一个，其余的上面的全部看成另外一个，然后可以层层套用2个盘子的异动情况。 另外要特别的写出只有一个盘子时候的情况

Answer 5