用递归来解决汉诺塔问题（超详细的个人解读）（Python）

一、递归的关键特征

1、存在一个或多个基例，基例不需要再次递归，它是确定的表达式（是一个能直接算出值的表达式）。

2、所有递归链要以一个或多个基例结尾。

二、汉诺塔问题

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一

根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一

根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

个人理解：首先A为初始柱子，B为过渡柱子，C为目标柱子。

（1）如果当前只有一个盘子，我们可以直接把它从A移动到C。此时也是递归中的基例

（2）如果有n个圆盘，那么我们可以构造出hannt（n，A,C,B）,表示n个柱子从A移动到C，此时B为中间过渡柱子。

第一步：先把A上n-1个柱子移动到B柱子上，此时C柱子为中间的过渡柱子（我们可以把n-1个柱子看作一个整体），这一步我们便可以用hannt（n-1，A,B,C）

第二步：此时A上只有一个圆盘（最底下的最大的圆盘），把A上的最后一个圆盘移动到C即可（此时C圆盘上为一个最大的圆盘）。我们可以用print函数来打印出来这一步。

第三步：再把B柱子上的n-1个圆盘移动到C柱子，此时A柱子为中间过渡柱子。这一步我们可以用hannt（n-1,B,C,A）

三、补充

（如有错误，请指出）：当把n-1个圆盘移动到B柱子，C柱子上只有一个最大的圆盘时候，相当于C柱子上没有（因为C柱子只有一个最大的圆盘），此时A柱子上为空柱子，这不便和n盘子时情形一样吗，只是A柱子与B柱子换了换位置。

四、代码

def hannt(n,a,c,b):
    if n==1:
        print("{}:{}->{}".format(1,a,c))
    else:
        hannt(n-1,a,b,c)
        print("{}:{}->{}".format(n,a,c))
        hannt(n-1,b,c,a)
hannt(3,"A","C","B")

结果：

1:A->C
2:A->B
1:C->B
3:A->C
1:B->A
2:B->C
1:A->C

五、递归的补充

1、字符串的逆序输出

代码（手机横屏看）：

def reverse(s):
    if s=="":
        return s
    else:
        return reverse(s[1:])+s[0]#s[0]是首字符，s[1:]是剩余字符串，将它们反向连接，可以得到反字符串
tf=input("请输入一个字符串:")
print(reverse(tf))

结果：

请输入一个字符串:abcdef
fedcba

2、斐波那契数列

代码：

def f(n):
    if n == 1 or n == 2 :
        return 1
    else :
        return f(n-1) + f(n-2)
n=eval(input("请输入一个整数："))
x=f(n)
print(x)

结果

请输入一个整数：5
5
>>> 
==================== RESTART: C:\Users\我的电脑\Desktop\样本.py ====================
请输入一个整数：2
1
>>> 
==================== RESTART: C:\Users\我的电脑\Desktop\样本.py ====================
请输入一个整数：10
55
>>> 
==================== RESTART: C:\Users\我的电脑\Desktop\样本.py ====================
请输入一个整数：9
34

转载：https://blog.csdn.net/overcomemyself/article/details/106564294