2024年6月2日发(作者：)

递归函数的例子

递归函数是一种在程序中重复调用自身的函数，多用于求解一些

复杂问题，递归函数本质上是解决问题的分解方式。当一个问题可以

转化为一系列小的子问题，每个子问题都大致相同，并且小问题的解

可以合并在一起得到整个问题的答案时，这时候就可以考虑使用递归

函数来解决问题。

递归函数例子

1.乘函数。阶乘函数用来计算一个数的阶乘，比如 n!。阶乘函

数的定义是 n!=n*(n-1)!。可以看到，它可以用递归的方式实现，如

果 n 为 0，那么 0!=1。如果 n>0，那么 n!=n*（n-1）!，即

n!=n*(n-1)*(n-2)*…*1。

def factorial(n):

# n is less than 0

if n<0:

return None

# n is 0, it is 1

elif n==0:

return 1

# n is more than 0

else:

# call the function itself with n-1

return n * factorial(n-1)

- 1 -

print(factorial(5))

2.诺塔函数。汉诺塔是一个古老的智力游戏，它被认为是一个“经

典的益智游戏”。它由三根柱子组成，柱子上有不同大小的圆盘，一

共有N个，盘子上有刻底数字1到n，一开始所有的盘子都放在第一

个柱子上，任务是将所有的盘子一个一个的移动到第三个柱子上，每

次只能移动一个盘子，而且小的盘子不能放在大的盘子上面。

可以发现该问题可以用递归来解决，把n个盘子看成一个组合，

将其分解成n-1个盘子和一个盘子，然后将前n-1个盘子移动到目标

柱子上，再将最后一个盘子移动到目标柱子上，然后将刚刚移动的

n-1个盘子再从目标柱子移动到最终的目标柱子即可。使用递归函数

实现，代码如下：

def hannuota(n, start, target, temp):

if n == 1:

print(Move disk + str(n) + from + start + to +

target)

else:

hannuota(n-1, start, temp, target)

print(Move disk + str(n) + from + start + to +

target)

hannuota(n-1, temp, target, start)

hannuota(3, A C B

结论

- 2 -

从上面的两个例子中可以看出，递归函数可以用来解决一些复杂

问题，一些复杂的问题可以拆解成一系列相似的子问题，然后用递归

函数实现，最终能够得到问题的解。递归函数具有较好的可读性，在

实现相对复杂的算法时具有很好的抽象能力，正确使用递归函数能大

大提高程序的运算效率，是高效的编程方式。除此之外，需要注意的

是，递归函数的实现中要添加递归终止条件，以减少重复调用，否则

容易耗费大量的资源，导致程序运行效率低下；此外，归的深度也要

尽量控制，以免发生堆栈溢出。

- 3 -