Python 递归函数
Jinku Hu
2023年1月30日
我们这节来学习 Python 递归函数。
什么是 Python 递归函数
递归函数是一个调用自身的函数，这个过程称为函数递归。比如，让我们计算数字 6 的阶乘。
6 * 5 * 4 * 3 * 2 * 1
在以下代码中，我们创建了一个递归函数，用来计算某个数字的阶乘。
def fact(n):
"""Recursive function to find factorial"""
if n == 1:
return 1
else:
return n * fact(n - 1)
a = 6
print("Factorial of", a, "=", fact(a))
Factorial of 6 = 720
函数 fact(n) 是一个递归函数，它用参数 n-1 调用自身，直到参数变为 1 为止，这就是计算阶乘的方法，即将数字乘以比这数字小 1 的数的阶乘，fact(n)=n*fact(n-1)，就得到了这个数字的阶乘。
在这个递归函数中，有一个结束条件，当数字变为 1 时，返回 1，不再继续调用函数自身，这样递归调用就是有限次数的调用。
在创建递归函数时，必须有一个这样的结束条件来终止递归调用。
递归次数限制
也许你已经注意到了，每次函数调用自身时，都需要一些内存来存储一些中间值。因此，递归函数比正常的非递归函数消耗更多的内存。Python 将递归调用次数限制设置为 3000。
>>> import sys
>>> sys.getrecursionlimit()
3000
如果递归次数超过 3000 次的话，它会触发 RecursionError。
def fact(n):
"""Recursive function to find factorial"""
if n == 1:
return 1
else:
return n * fact(n - 1)
print(fact(4000))
Traceback (most recent call last):
File "<pyshell#2>", line 1, in <module>
print(factorial(3000))
File "<pyshell#1>", line 5, in factorial
return n * factorial(n-1)
File "<pyshell#1>", line 5, in factorial
return n * factorial(n-1)
File "<pyshell#1>", line 5, in factorial
return n * factorial(n-1)
[Previous line repeated 989 more times]
File "<pyshell#1>", line 2, in factorial
if n == 1:
RecursionError: maximum recursion depth exceeded in comparison
移除递归限制的方法
你可以通过将递归限制次数设置为大于所需递归次数的数字来解除递归次数的限制。
import sys
sys.setrecursionlimit(5000)
def fact(n):
"""Recursive function to find factorial"""
if n == 1:
return 1
else:
return n * fact(n - 1)
print(fact(4000))
递归的优点
- 使用递归函数，可以将问题分解为子问题来轻松解决。
- 代码变得整洁干净。
递归的缺点
- 有时很难去设计和理解递归函数的逻辑。
- 解决每个子问题将花费大量时间，因此递归函数效率低下。
