Python理解递归的方法总结
作者:laozhang 发布时间:2022-06-10 03:31:08
递归
一个函数在执行过程中一次或多次调用其本身便是递归,就像是俄罗斯套娃一样,一个娃娃里包含另一个娃娃。
递归其实是程序设计语言学习过程中很快就会接触到的东西,但有关递归的理解可能还会有一些遗漏,下面对此方面进行更加深入的理解
递归的分类
这里根据递归调用的数量分为线性递归、二路递归与多重递归
线性递归
如果一个递归调用最多开始一个其他递归调用,我们称之为线性递归。
例如:
def binary_search(data, target, low, high):
"""
二分查找,对有序列表进行查找,如果找到则返回True,否则返回False
"""
if low > high:
return False
else:
mid = (low + high) // 2
if target == data[mid]:
return True
elif target < data[mid]:
return binary_search(data, target, low, mid - 1)
else:
return binary_search(data, target, mid + 1, high)
虽然在代码中有两个binary_search,但他们是不同条件执行的,每次只能执行一次,所以是线性递归。
二路递归
如果一个递归调用可以开始两个其他递归调用,我们称之为二路递归
例如:
def binary_sum(S, start, stop):
"""
二路递归计算一个序列的和,例如S[0:5],就像切片的范围一样
"""
if start >= stop:
return 0
elif start == stop - 1:
return S[start]
else:
mid = (start + stop) // 2
return binary_sum(S, start, mid) + binary_sum(S, mid, stop)
这个递归每次执行都会调用两次该函数,所以说是二路递归,每次递归后,范围缩小一半,所以该递归的深度是1+logn
多重递归
如果一个递归调用可以开始三个或者更多其他递归调用,我们称之为多重递归
例如:
import os
def disk_usage(path):
"""
计算一个文件系统的磁盘使用情况,
"""
total = os.path.getsize(path)
if os.path.isdir(path):
for filename in os.listdir(path):
childpath = os.path.join(path, filename)
total += disk_usage(childpath)
print('{0:<7}'.format(total), path)
return total
os.path.getsize为获得标识的文件或者目录使用的即时磁盘空间大小。我理解的是如果该标识的是一个文件,那么就是获得该文件的大小,如果是一个文件夹的话,那就是获得该文件夹的大小,但不包括文件夹里边的内容,就像是一个盒子中放了很多物品,但这里只计算了盒子的重量,但没有计算物品的重量,也就是计算了一个空盒子。所以这个递归函数中的递归调用次数取决于这一层文件或文件夹的数量,所以是多重递归。
递归的不足
递归的不足显然就是时间与空间的消耗 ,这篇文章中使用了缓存的方法减少了斐波那契数列的计算消耗,在这里我们使用另一种方式来改善那种坏的递归:
def fibonacci(n):
"""
斐波那契数列计算,返回的是一个元组
"""
if n <= 1:
return (n, 0)
else:
(a, b) = fibonacci(n - 1)
return(a + b, a)
将原来的二路递归改为了线性递归,减少了重复的计算。
python的最大递归深度
每一次递归都会有资源的消耗,每一次连续的调用都会需要额外的内存,当产生无限递归时,那就意味着资源的迅速耗尽,这明显是不合理的。python为了避免这种现象,在设计时有意的限制了递归的深度,我们可以测试一下
def limitless(n):
print('第' + str(n) + '次调用')
n += 1
return limitless(n)
limitless(1)
第988次调用
第989次调用
第990次调用
第991次调用
第992次调用
第993次调用
第994次调用
第995次调用
第996次调用
Traceback (most recent call last):
File “D:/github/Data-Structure/code/递归.py”, line 73, in
limitless(1)
File “D:/github/Data-Structure/code/递归.py”, line 70, in limitless
return limitless(n)
File “D:/github/Data-Structure/code/递归.py”, line 70, in limitless
return limitless(n)
File “D:/github/Data-Structure/code/递归.py”, line 70, in limitless
return limitless(n)
[Previous line repeated 992 more times]
File “D:/github/Data-Structure/code/递归.py”, line 68, in limitless
print(‘第' + str(n) + ‘次调用')
RecursionError: maximum recursion depth exceeded while calling a Python object
最终递归到996次停止了递归,也就是python的递归深度限制在了1000附近。
1000层的限制已经是足够的了,但是还是有可能限制到某些计算,所以python提供了一个修改限制的方
import sys
def limitless(n):
print('第' + str(n) + '次调用')
n += 1
return limitless(n)
print(sys.getrecursionlimit())#1000
sys.setrecursionlimit(2000)
limitless(1)
第1994次调用
第1995次调用
第1996次调用
Traceback (most recent call last):
File “D:/github/Data-Structure/code/递归.py”, line 70, in limitless
return limitless(n)
File “D:/github/Data-Structure/code/递归.py”, line 70, in limitless
return limitless(n)
File “D:/github/Data-Structure/code/递归.py”, line 70, in limitless
return limitless(n)
[Previous line repeated 995 more times]
File “D:/github/Data-Structure/code/递归.py”, line 68, in limitless
print(‘第' + str(n) + ‘次调用')
RecursionError: maximum recursion depth exceeded while calling a Python objec
可见把这个深度该为2000后便多了1000次调用,但这个深度显然不是设置多少就是多少,毕竟还有计算机CPU与内存的限制,比如吧深度改为10000,那么运行后
第3920次调用
第3921次调用
第3922次调用
第3923次调用
Process finished with exit code -1073741571 (0xC00000FD)
到达3923次便终止了,查询-1073741571发现是递归栈溢出的问题。
尾递归
如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码。
Python解释器在对于一次函数调用中,会使用一个栈帧来保存当前调用的函数的信息,如输入参数、返回值空间、计算表达式时用到的临时存储空间、函数调用时保存的状态信息以及输出参数。因此在递归的调用中,这种未执行完的函数会一层一层的占用大量的栈帧。如果将递归的调用放到函数执行的最后一步,那么执行完这步,该次函数的栈帧就会释放,调用函数的新栈帧就会替换掉之前的栈帧,所以无论调用的深度有多少次,都只会占用一个栈帧,那也就不会发生栈溢出的问题。这就是尾递归。
所以根据需要,尾递归必须是线性递归,并且递归调用的返回值必须立即返回。
拿一个阶乘递归函数举例
def factorial(n):
"""
阶乘递归函数
"""
if n == 0:
return 1
else:
return n * factorial(n - 1)
上边这个是一个普通的递归,下面把他改成尾递归的形式
def facttail(n, res):
"""
阶乘尾递归,res初始为1
"""
if n < 0:
return 0
elif n == 0:
return 1
elif n == 1:
return res
else:
return facttail(n - 1, n *res)
这个函数比之前那个还多了个res,第一种每次调用完要乘n,这里的res就起了相同的作用,由于尾递归每一层的栈帧要释放,所以通过res来作为相乘的过程。我个人认为尾递归的难度就在于参数的设计,因为它的前提条件就是调用后什么也不再执行了,所以要作为传递的东西就得提前通过参数设计传递,总之要想设计一个尾递归的算法还是需要好好思考一下的。
猜你喜欢
- 以下的文章主要介绍的是SQL Serve数据库到DB2连接服务器的实现过程,我们大家都知道不同数据库平台的互连,一般对其称之为数据库的异构服
- 本文实例讲述了Python使用内置json模块解析json格式数据的方法。分享给大家供大家参考,具体如下:Python中解析json字符串非
- NopCommerce为了实现松耦合的框架设计目的,使用了IOC框架:Autofac。据有人测试,Autofac是性能很好的IOC工具。1、
- 本文实例讲述了微信公众平台实现获取用户OpenID的方法。分享给大家供大家参考。具体分析如下:用户点击微信自定义菜单view类型按钮后,微信
- 方法一 :这个是我在站长工具的查询页面使用的防止频繁查询,刷新页面的代码!下面函数的功能是3秒内查询页面即刷新了页面,超过2次就提示!sea
- 如果你的电脑内存较小那么想在本地做一些事情是很有局限性的(哭丧脸),比如想拿一个kaggle上面的竞赛来练练手,你会发现多数训练数据集都是大
- 有。试试下面这个程序:saveip.asp<%Server.Scripttimeout = 1000On 
- windows删除jupyter notebook 没办法的办法pip uninstall jupyter -ypip uninstall
- 前言Sphinx是一款支持多种编程语言的文档生成工具,在python项目开发过程中,可以帮助开发者根据需求生成相应的说明文档,拿今天我们就基
- 最近在抓取http://skell.sketchengine.eu网页时,发现用requests无法获得网页的全部内容,所以我就用selen
- 1,jdk配置由于jdk官网的链接不直接支持wget,可以使用下面的方法下载jdk,其中jdk版本为jdk1.8.0_91:wget --n
- YAML是一种直观的能够被电脑识别的的数据序列化格式,容易被人类阅读,并且容易和脚本语言交互。YAML类似于XML,但是语法比XML简单得多
- ewebeditor支持兼容IE8 的方法方法:前几天ie8正式公布了,当天中午我就去下载了一个迫不急待的将自己的浏览器升级到ie8,偶还刻
- 最近在看《Effective Python》,里面提到判断字符串或者集合是否为空的原则,原文如下:Don't check for e
- 前言当多线程访问同一个公共资源时,如果涉及到修改该公共资源的操作就可能会出现由于数据不同步导致的线程安全问题。一般情况下我们可以通过给公共资
- 最近有个功能需要java与python之间的数据交互,java需要把参数传给python,然后python计算的结果返回给java.于是就写
- 如何制作一个WAP手机的WML网页?代码如下:<%@Language=VBScriptMaxNoAds = 10'
- 这篇文章主要介绍了python字符串替换re.sub()实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值
- 今天终于可以用wxPython开发GUI程序了,非常高兴。把其中的一些注意点写下来以供参考。在windows XP平台下,首先需要做以下环境
- 本文介绍了关于redux-saga中take使用方法详解,分享给大家,具体如下:带来一个自己研究好久的API使用方法.redux-saga中