汉诺塔详解过程和递归思想及举例（python代码）_python汉诺塔递归代码

省略问题描述…

• 但我们知道64个盘子的移动次数是18 446 744 073 709 551 615这是一个天文数字

解决办法：

我们最终解决的问题就是将a柱子原来由大到小从下到上排好序的圆盘通过b柱子移动到c柱子上即可
如图：

• 1先定义递归函数hanio(n,a,b,c),该方法表示将n个盘子从a柱子借助b柱子移动到c柱子。
• 若a柱子上只有一个盘子，此时n=1，则可以直接将盘子从a柱子移动到c柱子上，问题得到解决，但是我有个疑问，这种情况（也就是中间移动出现的过程），a柱子上也只有一个盘子，怎么理解呢？
  忽略，还没讲完，请看下面讲解！
  -
• 若a柱子上有一个以上的盘子，即n>1,此时需要考虑三个步骤。

1先将n-1个盘子从a柱子借助c柱子移动到b柱子，如图：

2.将a柱子上剩下的第n个盘子移动到c柱子上

3.将b柱子上的n-1个盘子借助a柱子上移动到c柱子上，最后完成移动！如图：

python代码

# 汉诺塔
def hannio(n,a,b,c):
    if n==1:
        print("move dish %d from %c to %c" % (n, a, c))
    else:
        hannio(n-1,a,c,b)
        print("move dish %d from %c to %c" % (n, a, c))
        hannio(n-1,b,a,c)

print(hannio(4,'a','b','c'))
1
2
3
4
5
6
7
8
9
10

递归函数返回值原理：

递归是什么？
原理：函数自己调用自己的过程，怎么理解呢？也就是函数可以调用函数里面的所有的函数包括本身。
举例：第一个是阶乘（factorial）,第二个是进制转换，看代码：

#阶乘和
def factorial(n):
    if n==1:
        return 1
    else:
        return n*factorial(n-1)
n=int(input())#输入一个整数
result=factorial(n)
print("数字%d的阶乘和为:%d"%(n,result))
1
2
3
4
5
6
7
8
9

#进制转换
def toStr2(n,base):

    convertString='0123456789ABCDEF'

    if n == 0:

        return ''
    else:

        return toStr2(n // base, base) + convertString[n % base]

n,m=map(int,input().split())
result=int(toStr2(n,m))
print("%d转化为%d进制后为:%d"%(n,m,result))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

ok，结束！