大学生自救数据结构与算法（py实现）——01递归

本文主要是介绍大学生自救数据结构与算法（py实现）——01递归，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

目录

递归

基本概念

工作原理

基本要素

优点

缺点

实现技巧

实例解析：计算阶乘

斐波那契数列

高效的斐波那契数列

python中的最大递归深度

二分查找

基本原理

性能分析

优化与变体

线性递归 

元素序列的递归求和

二路递归

二路递归的基本概念

典型应用

工作原理

多重递归 

示例：计算卡特兰数（Catalan Number）

尾递归

如何消除尾递归

示例：斐波那契数列

---

递归

递归是计算机科学中一种重要的编程技术，它允许函数或过程直接或间接地调用自身来解决问题。递归在处理分而治之（divide-and-conquer）策略、树形结构遍历、动态规划等场景时尤为有效。理解递归的关键在于把握好基本情况（base case）和递归情况（recursive case），以及如何通过自我调用来逐步逼近问题的解。下面将从递归的基本概念、工作原理、优缺点、实现技巧及实例等方面进行详细解析。

基本概念

递归的基本思想是将复杂的问题分解为多个相似但规模较小的子问题，直到这些子问题简单到可以直接求解（即基本情况）。每一个子问题的解决又依赖于更小子问题的求解，这个过程一直进行，直到达到基本情况并开始返回结果，层层回溯，最终组合成原问题的解。

工作原理

递归函数的工作原理可以形象地比喻为“剥洋葱”。每次函数调用都会增加一个新的“层”，当到达基本情况时，这一层开始返回，然后上一层继续执行，直至最外层获得最终答案。这个过程涉及到调用栈，每进入一次递归调用，就有一条新的记录压入调用栈，存储当前函数的状态（包括局部变量和下一条指令的位置）。当函数返回时，相关记录从栈中弹出，程序恢复到调用前的状态。

基本要素

• 基本情况（Base Case）：这是递归终止的条件，是最简单的情况，可以直接给出解答，不需要进一步递归。
• 递归情况（Recursive Case）：当问题不能直接解决时，将其拆分成一个或多个较小的子问题，并通过调用自身来解决这些子问题。
• 递归关系：明确每一次递归调用是如何接近基本情况的，以及如何通过子问题的解来构建原问题的解。

优点

1. 代码简洁：递归往往能以非常直观的方式表达复杂的算法，使得代码更加清晰易懂。
2. 问题分解：适用于解决那些自然递归定义的问题，如树的遍历、分治策略等。
3. 思维模式：递归提供了一种强大的思维工具，有助于理解和解决复杂问题。

缺点

1. 性能开销：由于函数调用的栈空间消耗和重复计算，递归可能比迭代效率低。
2. 栈溢出风险：深度过大的递归可能导致调用栈溢出。
3. 理解难度：对于初学者，递归逻辑可能难以理解和调试。

实现技巧

1. 优化递归效率：通过记忆化（memoization）减少重复计算，或者尾递归优化（在某些语言中有效）减少栈空间使用。
2. 确保递归终止：仔细设计基本情况，避免无限递归。
3. 理解递归深度：根据问题规模预估最大递归深度，防止栈溢出。

实例解析：计算阶乘

阶乘是一个经典的递归示例，n的阶乘（记作n!）定义为所有小于等于n的正整数的乘积。

递归实现如下：

def factorial(n):# 基本情况if n == 0 or n == 1:return 1# 递归情况else:return n * factorial(n-1)

这个函数不使用任何显式循环。迭代是通过函数的重复递归调用实现的。在这个定义中没有循环，因为函数只要被调用一次，它的参数就会变小一次。当达到基本情况的时候，递归结束。

斐波那契数列

计算斐波那契数列中的第n个数。斐波那契数列是这样一个序列：每个数字是前两个数字之和，序列的前两个数字通常是0和1。

def bad_fibonacci(n):# 基本情况if n <= 0:return 0elif n == 1:return 1# 递归情况else:return bad_fibonacci(n-1) + bad_fibonacci(n-2)# 计算斐波那契数列的第5项
print(bad_fibonacci(5))

这段代码在计算斐波那契数列时，会打印出每一次递归调用的深度和当前处理的n值。

不过，这种斐波那契公式的实现其实效率非常低，要是用这个来计算n个斐波那契数需要对这个函数进行指数级别的调用。它的时间复杂度为O(2^n) 众所周知指数大爆炸。

高效的斐波那契数列

我们之所以尝试使用这个不好的递归算法，是因为第n个斐波那契数取决于前两个值，Fn−1​和Fn−2​。但，计算出Fn-2后，计算Fn-1的调用需要先自身调用然后计算Fn-2。因为他不知道先前级别的调用中被计算的Fn-2的值，这个重复操作了。并且这两个调用也都需要重新计算Fn-3的值，Fn-1也一样的。那么就会导致时间复杂度为指数级。

那么，我们可以只进行一次递归调用。我们需要重新定义函数的期望值。我们先定义一个函数，这个函数负责返回一对连续的斐波那契数列（Fn，Fn-1）并且约定了Fn-1 = 0，而不是只返回一个值。

下面是个代码例子：

def good_fib(n):if n <= 1:return(n,0)else:(a,b) = good_fib(n-1)return(a+b,a)

这下我们把时间复杂度降为了O(n) 每次对于good_fib(n)函数的递归调用都使参数n减小1。
 

python中的最大递归深度

在Python中，默认的最大递归深度是有限制的，这个限制是为了防止无限递归导致程序崩溃或者资源耗尽。默认的最大递归深度可以通过sys模块的getrecursionlimit()函数查询，也可以通过setrecursionlimit(limit)函数来修改这个限制，但需要注意的是，不加控制地增大递归深度可能会导致程序崩溃（比如栈溢出错误）。

查询当前的最大递归深度：

import sys
print(sys.getrecursionlimit())

默认情况下，这个值通常设置为约1000至3000之间，具体数值可能根据不同的Python解释器版本和操作系统有所差异。

如果在编程中遇到“RecursionError: maximum recursion depth exceeded in comparison”这样的错误，就说明你的递归深度超过了Python的默认限制。此时，你可能需要考虑改用迭代方法，或者在必要时小心地调整递归深度限制。不过，通常推荐优化算法避免过深的递归，而不是简单地增加限制。

二分查找

二分查找是一种在有序数组中高效寻找特定元素的搜索算法。它的核心思想是通过不断将待查找区间对半划分，快速排除一半的可能性，以此减少搜索范围，直到找到目标元素或确定目标不存在。以下是二分查找的详细解析：

基本原理

1. 有序数组：二分查找的前提条件是数据必须事先排序。不论是升序还是降序，只要数组是有序的，就可以应用二分查找。

2. 区间划分：初始时，设定两个指针，left指向数组的起始位置，right指向数组的末尾位置。计算中间位置的索引 mid，通常是 (left + right) / 2 或者 (left + right) >> 1 避免整数溢出。

3. 比较与决策：将中间位置的元素与目标值进行比较：

   • 如果 array[mid] 等于目标值，查找成功，返回 mid。
   • 如果 array[mid] 小于目标值，说明目标值位于中间元素的右侧，因此将左边界移动到 mid + 1。
   • 如果 array[mid] 大于目标值，说明目标值位于中间元素的左侧，因此将右边界移动到 mid - 1。

4. 循环终止：重复上述过程，直到 left > right，此时说明目标值不在数组中。

下面是一个简单的二分查找算法实现示例： 

def binary_search(array, target):left, right = 0, len(array) - 1while left <= right:mid = (left + right) // 2if array[mid] == target:return midelif array[mid] < target:left = mid + 1else:right = mid - 1return -1  # 表示目标值不在数组中

 运行下面的可以进行可视化：

def binary_search(array, target):left, right = 0, len(array) - 1while left <= right:mid = (left + right) // 2if array[mid] == target:return midelif array[mid] < target:left = mid + 1else:right = mid - 1return -1  # 目标值不在数组中时返回-1# 示例数组（已按升序排列）
array_example = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]# 要查找的目标值
target_value = 15# 调用二分查找函数
index = binary_search(array_example, target_value)# 根据查找结果输出信息
if index != -1:print(f"目标值 {target_value} 在数组中的索引位置是: {index}")
else:print(f"目标值 {target_value} 不在数组中。")

可视化如下

性能分析

• 时间复杂度：二分查找的时间复杂度为O(log n)，其中n是数组的长度。这是因为每次迭代都将搜索范围减半，因此最多需要log2(n)+1次比较。

• 空间复杂度：二分查找的空间复杂度为O(1)，因为它只需要常数级别的额外空间来存储指针。

• 适用性：适用于静态数据结构，即数据不频繁插入或删除的场景。对于动态变化的数据，维护有序状态的成本可能较高。

优化与变体

• 递归实现：二分查找可以用递归方式实现，但需要注意递归深度可能导致栈溢出。

• 查找第一个/最后一个特定值：在找到目标值后，可以通过微调边界来找到数组中第一个或最后一个特定值。

• 查找插入位置：如果目标值不存在，二分查找同样可以快速找到目标值应插入的位置，以保持数组有序。

线性递归 

如果一个递归函数被设计成使得所述主体的每个调用至多执行一个新的递归调用，这被称为线性递归。到目前为止，在我们已经看到的递归函数中，阶乘函数的实现和good_fib函数是线性递归的一个明显的例子。更有趣的是，尽管在名称中叫“binary”，二分查找算法也是线性递归的一个例子。

元素序列的递归求和

元素序列的递归求和是指通过递归函数来计算一个数列所有元素的和。我们可以使用线性递归来解决该问题。例如，通过假设想要计算一个含有n个整数的序列S的和。如果n = 0，S中所有n个整数的总和是0；否则，序列S的和应该为S中的前n-1个整数的总和加上S中的最后一个元素。

def linear_sum(S,n):if n== 0:return 0 else:return linear_sum(S,n-1) +S[n-1]

 对于大小为n的输入，该函数执行了n+1次函数调用。因此，这需要O(n)的时间，因为它花费恒定的时间执行每次调用的非递归部分，并且这个算法的空间复杂度也是O(n)，正如在做出最后一次的递归调用（当n=0）时的递归追踪中，对n+1个活动记录的任何一个我们都使用固定数量的内存空间。

二路递归

通常指的是在解决计算机科学问题时，采用的一种分而治之的策略，通过将原问题分解为两个或更多的相似子问题来求解。这一概念广泛应用于算法设计中，特别是在排序、搜索、动态规划等领域。下面将详细探讨二路递归的概念、典型应用、工作原理及其优势和局限性。

二路递归的基本概念

在递归思想中，"二路"强调的是问题被分解成两个独立但结构相同（或相似）的子问题。每个子问题都继续按照同样的规则进一步分解，直到达到一个可以直接解决的基本情况（也称为递归基）。这一过程类似于树的分枝，每一层都将问题分为两个分支，直至达到叶子节点——即不需要再分割的简单情况。

典型应用

1. 二分查找：在有序数组中查找特定元素，每次比较中间元素，根据比较结果将搜索区间减半，这是一个典型的二路递归应用。

2. 归并排序：将数组分成两半分别排序，再将两个有序部分合并。递归地对每半部分排序，最终通过合并操作获得完全有序数组。

3. 快速排序：选择一个“基准”元素，将数组分为比基准小和比基准大的两部分，递归地在这两部分上重复上述过程，直到整个数组变得有序。

4. 分治法解决最大子序列和问题：将数组分为两部分，分别求出左半部分和右半部分的最大子序列和，以及跨越中间点的最大子序列和，最后取三者中的最大值。

工作原理

• 分解：将原问题分解为两个或多个规模较小，但结构与原问题相同或相似的子问题。
• 解决：递归地解决每一个子问题。如果子问题足够小，则直接解决（递归基）。
• 合并：将子问题的解合并为原问题的解。这一步在一些问题中是隐含的，如归并排序中合并两个有序数组；而在其他问题中，如最大子序列和，需要显式实现。

多重递归 

多重递归是指在同一个函数或多个互相调用的函数中，存在两个或以上的递归调用。这种递归形式比单一递归更为复杂，因为它涉及到多个递归路径，每个路径都有自己的递归链。多重递归通常用于解决那些可以自然分解为多个相互依赖的子问题的问题。

下面通过一个简单的例子来说明多重递归的概念：

示例：计算卡特兰数（Catalan Number）

卡特兰数是一系列自然数，广泛出现在组合数学中，有许多应用，例如解决括号序列问题、二叉树计数问题等。第n个卡特兰数C_n可以通过多重递归的方式定义如下：

这个定义表明计算第n个卡特兰数需要知道所有小于n的卡特兰数，因此构成了一个多重递归问题。

def catalan(n):if n == 0:return 1else:res = 0for i in range(n):res += catalan(i) * catalan(n - i - 1)return res# 测试代码
print(catalan(4))  # 应输出第4个卡特兰数，即14

在这个例子中，catalan 函数递归调用了自己两次（catalan(i) 和 catalan(n-i-1)），形成多重递归调用链。要注意的是，多重递归可能导致较高的时间复杂度和较大的内存消耗，特别是在没有适当优化的情况下（如记忆化技术），可能会遇到性能瓶颈甚至栈溢出的问题。因此，在实际应用中，应谨慎使用多重递归，并考虑是否有迭代或其他更高效的解决方案。

尾递归（Tail Recursion）是指在函数的递归调用中，递归调用是函数体中的最后一个操作，并且递归调用的结果直接作为本次函数调用的返回值，没有进行任何额外的操作。尾递归可以被编译器或解释器优化，以避免栈溢出问题，因为它们可以被转换为迭代循环，从而减少调用栈的大小。

尾递归

如何消除尾递归

消除尾递归通常是指通过优化代码结构，确保递归调用满足尾递归的条件，以便编译器或解释器能够自动优化。以下是一些技巧：

1. 确保递归调用是最后的操作：确保递归调用之后没有其他计算或操作。如果需要传递额外信息给下一次递归调用，应该通过参数传递，而不是在递归调用后处理。

2. 直接返回递归调用的结果：递归调用的结果应该是函数的直接返回值，而不是在递归调用后再进行处理。

示例：斐波那契数列

原始的递归实现不是尾递归的，因为它在递归调用之后还进行了加法操作：

def fibonacci(n):if n <= 1:return nelse:return fibonacci(n-1) + fibonacci(n-2)

 改为尾递归的形式：

def fibonacci_tail(n, a=0, b=1):if n == 0:return aelse:return fibonacci_tail(n-1, b, a+b)

在这个尾递归版本中，fibonacci_tail 函数直接以递归调用的结果作为返回值，没有进行额外的操作，且所有的状态都通过参数传递，这使得它成为尾递归，理论上可以被编译器或解释器优化以减少资源消耗。

 那么，这一期 大学生数据结构与算法（py实现）——01递归就结束了。后续我会继续更新，请大家耐心等待！

这篇关于大学生自救数据结构与算法（py实现）——01递归的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---