Python递归调用应用实例-汉诺塔

递归介绍

1.简单的说：递归就是函数自己调用自己，每次调用时传入不同的值
2.递归有助于编程者解决复杂问题，同时可以让代码变得简洁

汉诺塔传说

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石住子，在一根柱子上从上往下按照大小顺序摞着64片圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一个柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
假如每秒钟移动一次，工序多长事件呢？移完这些金片需要5845.54亿年以上，太阳系的预期寿命据说也就数百亿年。

汉诺塔代码实现

def hanoi_tower(num, a, b, c):
    """
    输出指定的num个盘子移动的顺序
    :param num:指定盘子数
    :param a:表示A柱子
    :param b:表示B柱子
    :param c:表示C柱子
    :return:返回盘子移动的顺序
    """
    # 如果只有一个盘子
    if num == 1:
        print(f"第1个盘从: {a}移到{c}")
    else:
        # 有多个盘，我们认为只有两个，上面所有的盘和下面的一个盘
        # 移动上面所有的盘到B柱子，这个过程会借助到C柱子
        hanoi_tower(num - 1, a, c, b)
        # 移动最下面的盘
        print(f"第{num}个盘从: {a}移到{c}")
        # 移动B柱子上面所有的盘到C柱子，这个过程会借助到A柱子
        hanoi_tower(num - 1, b, a, c)


# 测试
n = int(input("请输入盘子的数量："))
hanoi_tower(n, 'A', 'B', 'C')

测试结果

汉诺塔游戏网址

可以登录下面的汉诺塔网站按照程序运行的结果进行验证：

https://www.novelgames.com/zh/tower/

递归重要规则

1.执行一个函数时，就创建一个新的空间（栈空间）
2.函数的变量时独立的，比如n变量
3.递归必须向退出递归的条件逼近，否则就无限递归，就会出现RecursionError:maximum recursion depth exceeded
4.当一个函数执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁