递归与汉诺塔问题

一. 递归

两个特点:

  1. 函数自己调用自己

  2. 要有结束条件 下面给两个递归函数来猜一下运行的结果

def func1(n):
    if n > 0: 
        print(n)
        func1(n - 1)
def func2(n):
    if n > 0:
        func2(n - 1)
        print(n)

如果n是3,猜一下两个函数的输出结果

func1(3)
func2(3)
3
2
1
1
2
3

递归实例: 汉诺塔问题

大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序着64片黄金圆盘大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘64根柱子移动完毕之日就是世界毁灭之时 当然这是个传说 下面我们来实现一下汉诺塔问题的实现过程

def hanoi(n, a, b ,c):
    if n > 0:
        hanoi(n - 1, a, c ,b)
        print("moving from %s to %s" % (a, c))
        hanoi(n - 1, b, a, c)
hanoi(3, 'A', 'B', 'C')
moving from A to C
moving from A to B
moving from C to B
moving from A to C
moving from B to A
moving from B to C
moving from A to C

对照着下面的动画演示我们来解释一下代码, 首先我们要知道,我们的圆盘是要从A移动到C的所以呢我们需要先hanoi(n - 1, a, c ,b)让我们的圆盘经过C, 然后我们再移动圆盘到B, 最后hanoi(n - 1, b, a, c)我们再将圆盘从B移动到C.

那么还有一种解释呢是我先将n-1个圆盘移动到B上面然后我的第n个盘子移动到C上面, 最后呢我在将n-1个盘子移动到C上面.