猫史档案馆

           有许多萌新在接触到python的函数递归时就十分头疼：这么多，我要算到什么时候去啊！

          实际上，递归并不难，我来给大家说说递归到底有什么用吧：首先，递归的核心思想是分治策略。分治，即 “分而治之”（divide and conquer），把一个复杂的问题分成两个或者更多相同的或者类似的子问题，直到最后的子问题可以简单地被直接求解，原问题就是子问题的解的合并。

         是不是
很复杂？不用急，我们用汉诺塔的问题来说明！

      有A、B、C三根柱子，A柱子上有n个圆盘，圆盘从下往上依次变小，要求照这样把A柱上的圆盘全部移到C柱，最终C柱也和A柱开始时一模一样。

          移动规则：1、一次只能移动1个。2、大圆盘不能在小圆盘上。

          看着好像十分复杂，但众所周知：把大象塞进冰箱里只用三步：1、打开冰箱门。2、把大象塞进去。3、关上冰箱门。我们现在也来分步骤：

          1、把n-1层圆盘移到B柱。

          2、把最底层的圆盘移到C柱。

          3、把B柱上的圆盘移到C柱上。

4-1=3，上面3个可以看做子问题来解答

现在开始写代码！

 

好了，代码大家可以复制：

def hanoi(n,a,b,c):#分别代表层数、起始位置、过渡位置和目标位置
    if n==1:
        print(a,'-->',c)
    else:
        hanoi(n-1,a,c,b)#第1步
        print(a,'-->',c)#第2步
        hanoi(n-1,b,a,c)#第三步

hanoi(3,'a','b','c')#有三层