Python 递归
提示
- Python递归的基础:递归是函数自我调用的过程,类似于两面镜子相对造成的无限反射。
- 递归函数示例:以阶乘函数为例,展示了递归如何通过逐步减少数值来简化问题。
- 递归的利弊:虽然递归可以简化代码和解决复杂问题,但可能导致逻辑难以理解和效率低下。
递归是用自身定义自身的过程。
一个现实世界的例子是将两面平行镜子相对放置。任何放在它们之间的物体都会被递归地反射。
Python递归函数
在Python中,我们知道一个函数可以调用其他函数。函数甚至可以调用自己。这种结构被称为递归函数。
下面的图片展示了一个名为recurse
的递归函数的工作原理。
以下是一个递归函数的例子,用来查找一个整数的阶乘。
一个数的阶乘是从1到该数的所有整数的乘积。例如,6的阶乘(表示为6!)是1*2*3*4*5*6 = 720。
递归函数的例子
def factorial(x):
"""这是一个递归函数
用来查找一个整数的阶乘"""
if x == 1:
return 1
else:
return (x * factorial(x-1))
num = 3
print("The factorial of", num, "is", factorial(num))
输出
3的阶乘是6
在上面的例子中,factorial()
是一个递归函数,因为它调用了自己。
当我们用一个正整数调用这个函数时,它会通过递减的方式递归地调用自己。
每个函数都会将数字与它下面的数的阶乘相乘,直到它等于1。这个递归调用可以用以下步骤解释。
factorial(3) # 第1次调用,传入3
3 * factorial(2) # 第2次调用,传入2
3 * 2 * factorial(1) # 第3次调用,传入1
3 * 2 * 1 # 从第3次调用返回,因为数字=1
3 * 2 # 从第2次调用返回
6 # 从第1次调用返回
让我们来看一个展示递归过程的逐步图片:
我们的递归在数字减少到1时结束。这被称为基础条件。
每个递归函数都必须有一个停止递归的基础条件,否则函数会无限地调用自己。
Python解释器限制了递归的深度,以帮助避免无限递归,从而导致堆栈溢出。
默认情况下,递归的最大深度是1000。如果超过限制,会导致RecursionError
。让我们看一个这样的情况。
def recursor():
recursor()
recursor()
输出
Traceback (most recent call last):
File "<string>", line 3, in <module>
File "<string>", line 2, in a
File "<string>", line 2, in a
File "<string>", line 2, in a
[上一行重复了996次]
RecursionError: 超出了最大递归深度
递归的优点
- 递归函数使代码看起来清洁且优雅。
- 使用递归可以将复杂任务分解为更简单的子问题。
- 使用递归生成序列比使用一些嵌套迭代更容易。
递归的缺点
- 有时候递归背后的逻辑难以跟随。
- 递归调用开销大(效率低),因为它们占用了大量内存和时间。
- 递归函数难以调试。