Python理解递归的方法总结

　　

<强>递归

　　

一个函数在执行过程中一次或多次调用其本身便是递归,就像是俄罗斯套娃一样,一个娃娃里包含另一个娃娃。

　　

递归其实是程序设计语言学习过程中很快就会接触到的东西,但有关递归的理解可能还会有一些遗漏、下面对此方面进行更加深入的理解

　　

<强>递归的分类

　　

这里根据递归调用的数量分为线性递归,二路递归与多重递归

　　

<强>线性递归

　　

如果一个递归调用最多开始一个其他递归调用,我们称之为线性递归。

　　

例如: 　　 　　 　　def binary_search(数据、目标、低、高): 　　”“” 　　二分查找,对有序列表进行查找,如果找到则返回真,否则返回错误的 　　”“” 　　 　　如果低比;高: 　　返回假 　　其他:=(低+高)/中期/2 　　如果目标==数据(中期): 　　还真 　　elif目标& lt;数据(中期): 　　返回binary_search(数据、目标低,1)中期 　　其他: 　　返回binary_search(数据、目标、中期+ 1,高) 　　 　　

虽然在代码中有两个binary_search,但他们是不同条件执行的,每次只能执行一次,所以是线性递归。

　　

<强>二路递归

　　

如果一个递归调用可以开始两个其他递归调用,我们称之为二路递归

　　

例如: 　　 　　 　　def binary_sum(年代,启动、停止): 　　”“” 　　二路递归计算一个序列的和,例如年代0:5,就像切片的范围一样 　　 　　”“” 　　 　　如果开始祝辞=站: 　　返回0 　　elif开始==停止- 1: 　　返回S[开始] 　　其他: 　　中期=(启动+停止)//2 　　开始,返回binary_sum(年代,中期)+ binary_sum(年代,中期,停止) 　　 　　

这个递归每次执行都会调用两次该函数,所以说是二路递归,每次递归后,范围缩小一半,所以该递归的深度是1 + logn

　　

<强>多重递归

　　

如果一个递归调用可以开始三个或者更多其他递归调用,我们称之为多重递归

　　

例如: 　　 　　 　　进口操作系统 　　 　　def disk_usage(路径): 　　”“” 　　计算一个文件系统的磁盘使用情况, 　　 　　”“” 　　 　　总=os.path.getsize(路径) 　　如果os.path.isdir(路径): 　　在os.listdir文件名(路径): 　　childpath=os.path。加入(路径,文件名) 　　总+=disk_usage (childpath) 　　打印(' {0:& lt; 7}’.format(总),路径) 　　返回总 　　 　　

os.path.getsize为获得标识的文件或者目录使用的即时磁盘空间大小。我理解的是如果该标识的是一个文件,那么就是获得该文件的大小,如果是一个文件夹的话,那就是获得该文件夹的大小,但不包括文件夹里边的内容,就像是一个盒子中放了很多物品,但这里只计算了盒子的重量,但没有计算物品的重量,也就是计算了一个空盒子,所以这个递归函数中的递归调用次数取决于这一层文件或文件夹的数量,所以是多重递归。

　　

<强>递归的不足

　　

递归的不足显然就是时间与空间的消耗,这篇文章中使用了缓存的方法减少了斐波那契数列的计算消耗,在这里我们使用另一种方式来改善那种坏的递归:

　　 　　 　　def斐波纳契(n): 　　”“” 　　斐波那契数列计算,返回的是一个元组 　　 　　”“” 　　 　　如果n & lt;=1: 　　返回(n, 0) 　　其他: 　　(a, b)=斐波纳契(n - 1) 　　返回(a + b) 　　 　　

将原来的二路递归改为了线性递归,减少了重复的计算。

　　

<强> python的最大递归深度

　　

每一次递归都会有资源的消耗,每一次连续的调用都会需要额外的内存,当产生无限递归时,那就意味着资源的迅速耗尽,这明显是不合理的.python为了避免这种现象,在设计时有意的限制了递归的深度,我们可以测试一下

　　 　　 　　def无限(n): 　　打印(“第”+ str (n) +“次调用的) 　　n +=1 　　返回无限(n) 　　无限的(1) 　　 　　

　　

第988次调用
　　第989次调用
　　第990次调用
　　第991次调用
　　第992次调用
　　第993次调用
　　第994次调用
　　第995次调用
　　第996次调用
　　回溯(最近调用最后):
　　文件“D:/github/数据结构/代码/递归。py”, 73行,在
　　无限的(1)
　　文件“D:/github/数据结构/代码/递归。py”, 70行,在无限的

Python理解递归的方法总结