探索Python中的递归概念
是否渴望深入了解编程中的递归奥秘？ 这篇关于Python递归的教程将为你打开大门。
递归是一种强大的问题解决技术，是每个程序员工具箱中不可或缺的利器。 尽管初学者可能觉得它难以掌握，但递归能够帮助我们为复杂的问题设计出更优雅的解决方案。
在本教程中，我们将以代码实践的方式学习Python中的递归。 我们将重点讨论以下内容：
- 递归的基本原理
- 递归函数的定义及其工作机制
- 使用Python实现递归函数
- 迭代与递归两种问题解决方式的差异
现在，让我们开始这段探索之旅吧！
什么是递归？
递归是一种编程技巧，它允许函数通过重复调用自身来解决问题。
本质上，递归是一种将复杂问题分解为更小、结构相似的子问题的方法。 它可以让你用简化的版本来处理问题。
那么，如何在代码中运用递归呢？ 为了解答这个问题，我们先来深入了解递归函数的工作原理。
理解递归函数
递归函数是在其定义中调用自身的函数。 每次递归调用都代表原问题的规模更小或复杂度更低的子问题。
为了确保递归过程最终能够终止，递归函数必须包含一个或多个基本情况。 基本情况是指函数停止调用自身并返回结果的条件。
让我们进一步剖析递归函数的构成要素：
- 基本情况：基本情况定义了一个或多个条件，当满足这些条件时，递归会停止。 当达到基本情况时，函数将返回结果，而不会进行进一步的递归调用。 基本情况对于避免无限递归至关重要。
- 递归情况：递归情况规定了如何将问题分解为更小的子问题。 在函数执行的这部分，函数会使用经过修改的输入值来调用自身。 因此，每次递归调用都是向基本情况逼近的一步。
接下来，我们将探讨调用递归函数时会发生什么。
递归的幕后机制
当一个函数被调用时，其执行上下文的记录会被放入调用栈中。 该记录包含了关于函数参数、局部变量以及函数执行完成后返回位置的信息。
对于递归函数，当函数调用自身时，一条新的记录会被添加到调用栈，有效地暂停了当前函数的执行。 调用栈使得Python能够追踪所有挂起的函数调用，包括来自递归调用的函数调用。
递归会持续进行，直到满足基本情况。 当基本情况返回结果时，函数调用会逐个解除 — 每个函数将其结果返回到调用栈的上一层。 这个过程会持续到初始函数调用完成。
在Python中实现递归
在本节中，我们将研究三个简单的递归示例：
- 计算一个数的阶乘
- 计算斐波那契数列中的数字
- 使用递归实现二分查找
对于每个例子，我们将描述问题、提供Python递归实现，并解释递归实现的工作原理。
#1. 使用递归计算阶乘
问题：计算一个非负整数 n 的阶乘，用 n! 表示。 数学上，一个数 n 的阶乘是从 1 到 n 所有正整数的乘积。
阶乘计算非常适合递归，其数学定义如下：
下面是用递归方式计算给定数字 n 的阶乘的函数：
def factorial(n):
# 基本情况
if n == 0 or n == 1:
return 1
# 递归情况：n! = n * (n-1)!
else:
return n * factorial(n - 1)
让我们计算 5!，使用`factorial()`函数:
factorial_5 = factorial(5)
print(factorial(5))
# 输出: 120
现在，我们来剖析一下这个函数的工作机制：
- 我们有一个基本情况，用于检查 n 是否等于 0 或 1。如果满足该条件，函数将返回 1。回想一下，0! 是 1，1! 也是如此。
- 如果 n 大于 1，我们通过将 n 乘以 n-1 的阶乘来计算 n!。 这表示为 n * factorial(n – 1)。
- 函数不断递归调用自身，每次都使用递减的 n 值，直到达到基本情况。
#2. 使用递归计算斐波那契数列
问题：查找斐波那契数列中第 n 个索引处的项。 斐波那契数列的定义如下：F(0) = 0, F(1) = 1, 对于 n >= 2，F(n) = F(n-1) + F(n-2)。
def fibonacciSeq(n):
# 基本情况
if n == 0:
return 0
elif n == 1:
return 1
# 递归情况: F(n) = F(n-1) + F(n-2)
else:
return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)
让我们运行这个函数：
fib_5 = fibonacciSeq(5)
print(fib_5)
# 输出: 5
该函数的工作方式如下：
- 我们先来讨论基本情况。 如果 n 为 0，则返回 0。如果 n 为 1，则返回 1。回忆一下 F(0) = 0 和 F(1) = 1。
- 在递归情况下，如果 n 大于 1，则函数通过将 F(n-1) 和 F(n-2) 项相加来计算 F(n)。 这表示为 fibonacciSeq(n – 1) + fibonacciSeq(n – 2)。
- 函数不断地使用递减的 n 值递归调用自身，直到达到基本情况。
#3. 二分查找的递归实现
问题：使用递归实现二分查找算法，以在已排序的列表中找到目标元素的位置。
以下是二分查找的递归实现：
def binarySearch(arr, target, low, high):
# 基本情况：未找到目标
if low > high:
return -1
mid = (low + high) // 2
# 基本情况：找到目标
if arr[mid] == target:
return mid
# 递归情况：搜索数组的左半部分或右半部分
elif arr[mid] > target:
return binarySearch(arr, target, low, mid - 1)
else:
return binarySearch(arr, target, mid + 1, high)
`binarySearch` 函数每次递归调用时都会将搜索区间分成两半，直到找到目标或者确定目标不在列表中。
下面是该函数的运行示例：
arr = [5, 8, 13, 24, 37, 49, 51, 64, 72, 88, 96]
target = 37
idx = binarySearch(arr, target, 0, len(arr)-1)
print(idx)
# 输出: 4
让我们来分解一下该函数的工作原理：
- 在二分查找的递归实现中，我们有两种基本情况。 首先，如果 `low` 变得大于 `high`，则意味着目标元素不在列表中。 因此，我们返回 -1 表示未找到目标。
- 另一个基本情况是检查当前搜索区间的中间索引 `mid` 处的元素是否等于目标。 如果它们匹配，我们返回索引 `mid`，表明我们已经找到了目标。
- 在递归情况下，如果中间元素大于目标，我们会通过调用 `binarySearch(arr, target, low, mid – 1)` 递归地搜索数组的左半部分。 如果中间元素小于目标，我们会通过调用 `binarySearch(arr, target, mid + 1, high)` 来搜索右半部分。
递归与迭代方法
迭代方法（使用循环）是解决问题的另一种常见方法。 那么，它与递归有何不同？ 让我们来比较一下。
首先，我们比较一个常见问题的递归和迭代解决方案：计算一个数的阶乘。
下面是阶乘计算的递归实现：
def factorialRec(n):
# 基本情况
if n == 0 or n == 1:
return 1
# 递归情况：n! = n * (n-1)!
else:
return n * factorial(n - 1)
因为我们知道一个非负数的阶乘是从 1 到 n 的所有数字的乘积，所以我们也可以使用循环来编写迭代实现。
def factorialIter(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
这两种实现都会给出相同的结果。
factorial_5 = factorialRec(5)
print(factorial_5)
# 输出: 120
factorial_5 = factorialIter(5)
print(factorial_5)
# 输出: 120
但是迭代方法是否优于递归方法呢？ 当存在深度递归（函数调用过多）时，您可能会因为超出递归深度而遇到错误。 对于递归实现需要太多函数调用才能达到基本情况的问题，循环是更好的选择。
我们来总结一下迭代和递归实现之间的差异：
| 特征 | 递归方法 | 迭代方法 |
| 结构 | 使用递归函数调用并依赖于调用栈。 | 使用循环进行迭代而无需额外的函数调用。 |
| 基本情况 | 需要显式基本情况来停止递归。 | 通常使用循环条件来终止。 |
| 性能 | 由于调用栈的原因，可能会降低内存效率。深度递归有时会导致堆栈溢出错误。 | 通常内存效率更高，并且不太容易出现堆栈溢出错误。 |
| 调试 | 由于多个函数调用和嵌套执行上下文，调试可能会很困难。 | 由于执行的线性流程简单，通常更容易调试。 |
结论
在本文中，我们首先学习了什么是递归以及如何使用基本情况和递归关系来定义递归函数。
然后，我们编写了一些Python代码 — 一些常见编程问题的递归实现。 最后，我们了解了迭代方法和递归方法之间的差异以及每种方法的优缺点。
接下来，可以参考这份Python面试问题列表。