Python - 递归：初学者指南
你好，未来的Python巫师们！今天，我们将踏上一段令人兴奋的旅程，进入递归的世界。如果这听起来有点吓人，别担心——我保证我们会让它变得既有趣又易于理解。所以，拿起你最喜欢的饮料，舒服地坐好，让我们开始吧！
什么是递归？
想象一下，你站在两面相对的镜子之间。你会看到无数次的反射，对吧？这在编程中有点像递归！简单来说，递归就是一个函数调用自己来解决问题。
让我们从一个简单的例子开始：
def countdown(n):
if n <= 0:
print("发射！")
else:
print(n)
countdown(n - 1)
countdown(5)如果你运行这段代码，你会看到：
5
4
3
2
1
发射！现在，让我们来分解一下：
- 我们定义了一个名为
countdown的函数，它接受一个数字n。 - 如果
n是0或更小，我们打印“发射！”。 - 否则，我们打印
n，然后再次调用countdown，参数为n - 1。
这就是递归的行动！函数不断用更小的数字调用自己，直到它达到零。
递归的组成部分
每个递归函数都有两个主要部分：
- 基本情况：这是停止递归的条件。
- 递归情况：这是函数调用自己的地方。
在我们的倒计时示例中：
- 基本情况是
if n <= 0 - 递归情况是
countdown(n - 1)
让我们看另一个经典的例子：计算阶乘。
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)
print(factorial(5)) # 输出：120这里发生了什么：
- 如果
n是0或1，我们返回1（这是我们的基本情况）。 - 否则，我们将
n乘以n - 1的阶乘（这是我们的递归情况）。
所以，factorial(5)变成：
5 factorial(4)
5 (4 factorial(3))
5 (4 (3 factorial(2)))
5 (4 (3 (2 factorial(1))))
5 (4 (3 (2 1)))
5 4 3 2 1 = 120
递归的力量
递归可以使一些复杂的问题变得容易解决。让我们看一个稍微高级一点的例子：斐波那契数列。
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
for i in range(10):
print(fibonacci(i), end=" ")
# 输出：0 1 1 2 3 5 8 13 21 34这个函数计算第n个斐波那契数。斐波那契数列从0和1开始，每个后续的数字都是前两个数字的和。
使用递归的二分查找
现在，让我们解决一个更实际的问题：二分查找。这是一种在排序列表中查找项目的高效方法。
def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1
arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, 0, len(arr)-1, x)
if result != -1:
print(f"元素存在于索引 {result}")
else:
print("元素不在数组中")这个函数通过反复将搜索区间减半来工作。如果搜索键的值小于区间中间的项，则将区间缩小到下半部分。否则，缩小到上半部分。反复检查，直到找到值或区间为空。
何时使用递归
递归特别适用于以下情况：
- 可以分解为类似子问题的问题
- 树状数据结构（例如，文件系统，HTML DOM）
- 类似QuickSort，MergeSort等的算法
然而，递归并不总是最佳解决方案。对于非常深的递归，它可能需要大量的内存，有时一个简单的循环可能更有效且更容易理解。
递归方法表
| 方法 | 描述 | 示例 |
|---|---|---|
| 直接递归 | 函数直接调用自己 | 我们的countdown和factorial示例 |
| 间接递归 | 函数A调用函数B，然后函数B调用函数A | 见下面的示例 |
| 尾递归 | 递归调用是函数执行的最后一件事 | 我们的countdown示例 |
| 非尾递归 | 递归调用不是函数执行的最后一件事 | 我们的factorial示例 |
以下是间接递归的示例：
def is_even(n):
if n == 0:
return True
else:
return is_odd(n - 1)
def is_odd(n):
return not is_even(n)
print(is_even(4)) # 输出：True
print(is_odd(4)) # 输出：False在这个例子中，is_even调用is_odd，然后is_odd调用is_even。
结论
恭喜你！你刚刚迈入了令人着迷的递归世界的第一步。记住，像任何强大的工具一样，递归应该明智地使用。它可以使你的代码更优雅，轻松解决复杂问题，但也可能使简单问题变得不必要的复杂。
在你继续Python之旅的过程中，你会遇到许多可以应用递归的情况。继续练习，很快你就能像专业人士一样递归了！
Credits: Image by storyset