递归思想——关于递归的多个例子详解

发布时间：2024-11-23 20:55

思想启发源于生活，又回归于生活 #生活乐趣# #生活体验# #读书生活感悟# #思想启发#

阶乘

举个例子，我们来计算阶乘 n! = 1 * 2 * 3 * … * n，用函数 fact(n)表示，可以看出：
fact(n) = n! = 1 * 2 * 3 * ... * (n-1) * n = (n-1)! * n = fact(n-1) * n

于是，fact(n)用递归的方式写出来就是：

def fact(n): if n==1: return 1 return n * fact(n - 1) 1234

如果我们计算fact(5)，可以根据函数定义看到计算过程如下

汉诺塔问题

我们对柱子编号为a, b, c，将所有圆盘从a移到c可以描述为：
如果a只有一个圆盘，可以直接移动到c；
如果a有N个圆盘，可以看成a有1个圆盘（底盘） + (N-1)个圆盘，首先需要把 (N-1) 个圆盘移动到 b，然后，将 a的最后一个圆盘移动到c，再将b的(N-1)个圆盘移动到c。
请编写一个函数，给定输入 n, a, b, c，打印出移动的步骤：
move(n, a, b, c)
例如，输入 move(2, ‘A’, ‘B’, ‘C’)，打印出：
A --> B
A --> C
B --> C

def move(n,a,b,c): if n==1: #这其实是只有一个圆盘需要从A到C的情况。所有递归，最终都是走到这一步。 print (a,'-->',c) #这是结束递归，省略了None。没有这句的话，递归没办法结束。 return #将A柱的n-1个盘移到B柱，这里毫无争议。注意形参顺序变化了。 move(n-1,a,c,b) #这句话才是第一个柱子的第n个圆盘移动到目标柱子。 print a,'-->',c #过渡柱子B上（n-1）个圆盘B递归移动到目标柱子C move(n-1,b,a,c)) 123456789101112

move(4,‘A’,‘B’,‘C’)
在这里插入图片描述