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

2024-06-24 05:52

本文主要是介绍大学生自救数据结构与算法(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递归的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1089345

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别: 当你在一个模块(文件)中使用 global 声明变量时,这个变量只在该模块的全局命名空

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time