想了解编程中的递归的所有知识吗？ 本关于 Python 递归的教程将帮助您入门。
递归是一种非常有用的解决问题的技术，可以添加到程序员的工具箱中。 虽然最初通常很难理解，但递归可以帮助您为复杂问题提出更优雅的解决方案。
在本教程中，我们将采用代码优先的方法来使用 Python 学习递归。 我们将特别介绍：
- 递归的基础知识
- 递归函数及其工作原理
- 递归函数的Python实现
- 迭代和递归解决问题的方法之间的差异
让我们开始吧！
目录
什么是递归？
递归是一种编程技术，其中函数重复调用自身来解决问题。
从本质上讲，递归是一种解决问题的方法，涉及将复杂问题分解为更小的、相同的子问题。 本质上，它允许您用更简单的版本来解决问题。
那么，我们如何在代码中实现递归呢？ 为此，让我们了解递归函数的工作原理。
理解递归函数
我们定义一个递归函数，在其定义中调用自身。 每个递归调用都代表原始问题的更小或更简单的版本。
为了确保递归最终终止，递归函数必须包含一个或多个基本情况，即函数停止调用自身并返回结果的条件。
让我们进一步分解一下。 递归函数包括：
- 基本情况：基本情况是确定递归何时停止的一个或多个条件。 当满足基本情况时，该函数将返回结果，而不进行任何进一步的递归调用。 基本情况对于防止无限递归至关重要。
- 递归案例：递归案例定义了如何将问题分解为更小的子问题。 在函数的这一部分中，函数使用修改后的输入调用自身。 因此，每次递归调用都是达到基本情况的一步。
接下来，我们讨论一下调用递归函数时会发生什么。
递归的幕后工作原理
当一个函数被调用时，它的执行上下文的记录被放置在调用堆栈上。 该记录包括有关函数参数、局部变量以及函数完成执行后返回位置的信息。
对于递归函数，当函数调用自身时，一条新记录会被推送到调用堆栈上，从而有效地暂停当前函数的执行。 堆栈允许 Python 跟踪所有挂起的函数调用，包括来自递归调用的函数调用。
直到达到基本情况，递归才会继续。 当基本情况返回结果时，函数调用将被逐个解析 – 每个函数将其结果返回到调用堆栈的上一层。 此过程将持续到初始函数调用完成。
在 Python 中实现递归
在本节中，我们将探讨三个简单的递归示例：
对于每个示例，我们将说明问题，提供 Python 递归实现，然后解释递归实现的工作原理。
#1. 使用递归进行阶乘计算
问题：计算非负整数n的阶乘，记为n!。 从数学上讲，数字 n 的阶乘是从 1 到 n 的所有正整数的乘积。
阶乘计算非常适合递归，如下所示：
下面是计算给定数字 n 的阶乘的递归函数：
def factorial(n):
# Base case
if n == 0 or n == 1:
return 1
# Recursive case: n! = n * (n-1)!
else:
return n * factorial(n - 1)
我们来计算 5！ 使用阶乘()函数：
factorial_5 = factorial(5) print(factorial(5)) # Output: 120
现在让我们看看该函数是如何工作的：
- 我们有一个基本情况，用于检查 n 是否等于 0 或 1。如果满足条件，函数将返回 1。回想一下 0！ 是 1，1! 也是如此。
- 如果n大于1，我们计算n！ 将 n 乘以 n-1 的阶乘。 这表示为 n * 阶乘(n – 1)。
- 该函数不断以递减的 n 值进行递归调用，直到达到基本情况。
#2. 斐波那契数列的递归
问题：找到第 n 个索引处的项 斐波那契数列。 斐波那契数列定义如下：F(0) = 0、F(1) = 1，并且当 n >= 2 时，F(n) = F(n-1) + F(n-2)。
def fibonacciSeq(n):
# Base cases
if n == 0:
return 0
elif n == 1:
return 1
# Recursion: F(n) = F(n-1) + F(n-2)
else:
return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)
让我们运行该函数：
fib_5 = fibonacciSeq(5) print(fib_5) # Output: 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):
# Base case: target not found
if low > high:
return -1
mid = (low + high) // 2
# Base case: target found
if arr[mid] == target:
return mid
# Recursive case: search left or right half of the array
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) # Output: 4
让我们分解一下该函数的作用：
- 在二分搜索递归实现中，我们有两种基本情况。 首先，如果 low 变得大于 high，则意味着目标元素不在列表中。 因此，我们返回-1表示没有找到目标。
- 另一个基本情况检查当前搜索间隔的中间索引 mid 处的元素是否等于目标。 如果它们匹配，我们返回索引 mid，表明我们已经找到目标。
- 在递归情况下，如果中间元素大于目标，我们通过调用binarySearch(arr, target, low, mid – 1)递归搜索数组的左半部分。 如果中间元素小于目标，我们通过调用binarySearch(arr, target, mid + 1, high)来搜索右半部分。
递归与迭代方法
迭代方法（使用循环）是解决问题的另一种常见方法。 那么，它与递归有什么不同呢？ 让我们来看看吧。
首先，我们比较一个常见问题的递归和迭代解决方案：计算数字的阶乘。
下面是阶乘计算的递归实现：
def factorialRec(n):
# Base case
if n == 0 or n == 1:
return 1
# Recursive case: 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) # Output: 120 factorial_5 = factorialIter(5) print(factorial_0) # Output: 120
但是迭代方法是否优于递归方法？ 当存在深度递归（函数调用过多）时，您可能会因为超出递归深度而遇到错误。 对于递归实现需要太多函数调用才能达到基本情况的问题，循环是更好的选择。
让我们总结一下迭代和递归实现之间的区别：
特征递归方法迭代方法结构使用递归函数调用并依赖于调用堆栈。使用循环进行迭代而无需额外的函数调用。基础案例需要显式基础案例来停止递归。通常使用循环条件来终止。性能由于调用堆栈的原因可能会降低内存效率。 深度递归有时会导致堆栈溢出错误。通常，内存效率更高，并且不太容易出现堆栈溢出错误。调试由于多个函数调用和嵌套执行上下文，调试可能会很困难。由于执行的线性流程简单，通常更容易调试.迭代与递归方法
结论
在本文中，我们首先学习什么是递归以及如何使用基本情况和递归关系定义递归函数。
然后我们编写了一些 Python 代码——常见编程问题的递归实现。 最后，我们了解了迭代方法和递归方法之间的差异以及每种方法的优缺点。
接下来，查看这份 Python 面试问题列表。