[Python知识库]python实现汉诺塔--递归

原理解析

将最底层的盘子当作一个整体part2，其上的所有盘子当作一个整体part1。
将part1整体放入B柱子；将part2放入C柱子；后续递归地解决part1部分即可。

代码

def hano(n,a,b,c):
    """
        汉诺塔，将圆盘从a-->c 每次移动一个，小的一直在大的上方
        n，a柱的圆盘数
        a，a柱子
        b，b柱子
        c，c柱子
        函数打印移动顺序
        难点：
        1. 分别从n为1，2，3时 进行理解
        2. 函数执行时，传入实参；函数体内部执行时，使用的形参
    """
    # a柱子只有一个盘子，递归中明确的结束条件
    if n == 1:
        print("%s 号从 %s 移动到%s 位置"%(n,a,c))
    # 有一个以上的盘子，将第一个盘子以上的部分当作一个整体
    if n > 1:
        #移动最底层盘子以上的n-1个盘子，将其当作一个整体，移动到b
        hano(n-1,a,c,b)  #实际调用是实参，函数体内部是形参
        #然后将最底层的这个盘子移动到c
        print("%s 号从 %s 移动到%s 位置"%(n,a,c))

        #然后将n-1个盘子，从b移动到c
        hano(n-1,b,a,c)


hano(3,"A","B","C")

递归的要点

1. 要有明确的结束条件
2. 函数执行，需压栈，递归层数过多会导致效率低。