详解python中递归函数
作者:都枯槐 发布时间:2022-04-17 19:40:55
函数执行流程
def foo1(b,b1=3):
print("foo1 called",b,b1)
def foo2(c):
foo3(c)
print("foo2 called",c)
def foo3(d):
print("foo3 called",d)
def main():
print("main called")
foo1(100,101)
foo2(200)
print("main ending ")
函数执行过程:
全局帧中生成foo1、foo2、foo3、main函数对象
main函数调用
main中查找内建函数print压栈,将常量字符串压栈,调用函数,弹出栈顶,返回值。
main中全局查找foo1压栈,将常量100、101压栈,调用函数foo1,创建栈帧。print函数压栈,字符串和变量b、b1压栈,调用函数,弹出栈顶,返回值。
main中全局查找foo2函数压栈,将常量200压栈,调用foo2,创建栈帧。foo3函数压栈,变量c引用压栈,调用foo3函数,创建栈帧,foo3中内建函数中查找print压栈,将字符常量和变量d压栈。foo3完成print函数调用后返回。foo2恢复调用,执行print后,返回值,main中foo2调用结束后弹出栈顶,main继续执行print函数调用,弹出栈顶,main函数返回
函数中压栈,执行流程。
递归Recursion
函数直接或者间接调用自身就是递归
递归需要有边界条件、递归前进段,递归返回段
递归一定需要有边界条件
当边界条件不满足的时候,递进前进
当边界条件满足的时候,递归返回
递归要求
递归一定要有退出条件,递归调用一定执行到这个退出条件。没有退出条件的递归调用,就是无限调用
递归调用的深度不宜过深
python对递归调用的深度做了限制,以保护解释器,cpython中递归深度为1000,ipython中递归深度为3000
超过递归深度限制,抛出RecursionError:maxinum recursion depth exceeded 超出最大深度
sys.getrecursionlimit()是显示最大限制
对于基于前面或者换位置的时候使用封装和解构更有效
斐波那契数列实现(f(1)=1,f(2)=1,f(3)=f(1)+f(2),f(4)=f(2)+f(3)……)
#斐波那契数列普通循环实现
a,b=0,1
for i in range(4):
a,b=b,a+b
print(a)
#斐波那契数列函数递归实现
def foo(n): #大量的重复计算
return 1 if n<3 else foo(n-1)+foo(n-2)
#斐波那契数列函数循环实现
def fn(n,a=0,b=1):
a,b=b,a+b
if n==1:
return a
return fn(n-1,a,b)
递归的性能
循环稍微复杂一些,但是只要不是死循环,可以多次迭代直至算出结果
递归还有深度限制,如果递归复杂,函数反复压栈,栈内存很快会溢出
间接递归
def foo1():
foo2()
def foo2():
foo1()
间接递归,是通过别的函数调用了函数自身,但是如果构成了循环递归调用是非常危险的,但是往往这种情况在代码复杂的情况下,还是有可能发生这种调用的,要用代码的规范来避免这种递归调用的发生
递归总结
递归是一种很自然的表达,符合逻辑思维
递归相对运行效率低,每一次调用函数都要开辟新的栈帧
递归有深度限制,如果递归层次太深,函数反复压栈,栈内存很快就溢出了
如果是有限次数的递归,可以使用递归调用,或者使用循环代替,循环代码稍微复杂一些,但是只要不是死循环,过次迭代直至算出结果
绝大多数递归,都可以使用循环实现
即使递归代码很简洁,能不用尽量不使用递归
以上所述是小编给大家介绍的python递归函数详解整合网站的支持!
来源:https://blog.csdn.net/qq_36883141/article/details/89319035
猜你喜欢
- 我目标文件夹下有一大批图片,我要把它转变为指定尺寸大小的图片,用pthon和opencv实现的。以上为原图片。import cv2impor
- 正则表达式中的符号符号描述re1 | re2匹配正则表达式 re1 或者 re2 ;re1 与 re2 代表两个匹配的字符串信息^匹配字符串
- 这样处理的弊端是:如果数据量大,子分类很多,达到4级以上,这方法处理极端占用数据库连接池 对性能影响很大。 如果用SQL下面的CTE递归处理
- 一,前言我们现在拿到了一个十分庞大的数据集。是json文件,里面存储了将近十万个数据,现在要对其中的数据进行清洗处理。二,python模块i
- Msg 102, Level 15, State 1, Line 3 Incorrect syntax near '+'.
- 如何侦测HTTP表头信息?可用下列办法侦测并显示所有的HTTP HEADERS:<HTML><HEAD><TI
- 本文实例讲述了Python将阿拉伯数字转换为罗马数字的方法。分享给大家供大家参考。具体实现方法如下:def numToRomanNum(Nu
- 本文实例为大家分享了js实现鼠标切换图片的具体代码,供大家参考,具体内容如下实现效果,可以利用鼠标移动在对应的小点点上,或者点击左右两侧的箭
- 遇到一个很实际的问题:由于不想增加目录的深度,减少磁盘寻址的时间,需要减少一些目录层级。大家都知道建立文件夹是为了让文件管理更加的方便,现在
- 通过APIView进入找到Request的源码可以看见一堆属性和方法,其中request.data其实是一个方法,被包装成一个属性继续看__
- 随着python的发展越来越好,用python的伙伴也越来越多。本人刚开始接触python的时候用的第一个集成环境就是Anaconda,因为
- 当你在IE中点击一个Realplayer连接时,系统会自动启动Realplayer软件,不仅占用系统内存,而且在上网时Realplayer容
- Session作用Session的根本作用就是在服务端存储用户和服务器会话的一些信息。典型的应用有:1、判断用户是否登录。2、购物车功能。s
- 什么是pyc文件pyc是一种二进制文件,是由py文件经过编译后,生成的文件,是一种byte code,py文件变成pyc文件后,加载的速度有
- Dreamweaver(以下简称DW)提供了一种称为“Behavior”(行为)的机制,帮助你构建页面
- 如下所示:<span style="font-size:18px;"></span>import
- 疫情肆虐,憋在家实在无聊,索性写点东西,于是就有了这个极极极极极简的音乐播放器。这个极极极简的音乐播放器类似于“阅后即焚”的软件,播放器可以
- 前2种方法主要用到了列表解析,性能稍差,而最后一种使用的时候生成器表达式,相比列表解析,更省内存列表解析和生成器表达式很相似:列表解析[ex
- 最近给卫生局做一个表格上传/可视化系统,算是小有成果。今天把项目中的文件拖拽上传模块分离出来,做了一个独立的小demo,并把相关代码打包上传
- 首先:文章用到的解析库介绍BeautifulSoup:Beautiful Soup提供一些简单的、python式的函数用来处理导航、搜索、修