尾递归优化原理与Python实现(以Fibonacci数列和小明爬楼梯问题为例)_dongfuguo的博客-程序员宅基地

技术标签: 算法  python  tensorflow  计算机视觉  epoll  

首先祝全体屋友中秋节快乐!

众所周知,在函数递归调用时,要保存函数调用的位置以便使得被调函数结束后能够返回正确的位置,这个信息保存在线程栈中。由于栈的空间有限,所以如果函数递归调用深度超过一定限制,会导致栈崩溃。并且,如果需要保存大量返回位置并且逐级返回的话,也会耗费大量的时间,使得代码运行速度非常慢。

所谓尾递归,是指函数调用出现在函数的尾部最后一条语句,并且函数返回值不作为其他表达式的一部分。如果编译器支持尾递归优化的话,这种情况下将不会保存返回位置,从而避免栈崩溃。因此,通过改写递归函数,改用尾递归的话,会大幅度提高运行速度,并且不会栈崩溃。

例如,下面是经典的Fibonacci数列中第n项求解的问题,第一段代码没有使用尾递归,第二段代码使用了尾递归。

上面两段代码的运行速度有天壤之别,如下图所示:

bingo,太棒了,果然速度提高很多。

然而,不要高兴的太早,把代码中的n修改为1200,交换两个函数调用的顺序,重新测试结果如下:

还是栈崩溃。。。。

看来要真正实现尾递归优化,只是改写代码还不够啊,还需要编译器或解释器的支持才行。从上面的情况来看,Python解释器默认并没有支持尾递归优化。

网上有一个使用修饰器修改栈中参数实现尾递归优化的方法,不过代码是Python 2的,我进行了简单修改,变成了Python 3的版本。

为了验证代码的正确性,上面的代码同时给出了迭代法实现,并且把问题规模增大到2300,运行结果如下,可见迭代还是无敌的啊:

再例如,小明爬楼梯的问题,问题描述可以参考以前的推文Python两种方法求解登楼梯问题(京东2016笔试题),如果改为尾递归的话,继续使用上面代码中的尾递归修饰器,代码如下:

运行结果如下:

上面的实现看起来已经很完美了,但又是类定义,又是修饰器,还要操作栈帧,好像很复杂的样子,有没有更简单的实现呢?

答案是确定的,以小明爬楼梯的问题为例:使用嵌套函数定义+生成器函数实现尾递归优化的代码如下:

这样真的可以吗?我们让事实来说话,修改测试代码:

运行结果如下:

思考题:

1)文中的尾递归修饰器作用到普通递归函数上,会有作用吗?

2)所有递归函数都可以改成尾递归吗?试试组合数求解的递归函数,普通递归代码见针对递归函数的优化与Python修饰器实现,第一位成功改写为尾递归优化版本代码(或能够证明无法改写)并留言的屋友将获签名赠书一本,可以从董付国老师Python系列教材中任选一本:

  • 《Python程序设计(第2版)》清华大学出版社(2018年8月第9次印刷)

  • 《Python可以这样学》清华大学出版社(2018年7月第6次印刷)(本书已在台湾发行繁体版)

  • 《Python程序设计基础(第2版)》清华大学出版社(2018年9月第5次印刷)

  • 《中学生可以这样学Python》清华大学出版社(2018年5月第2次印刷)

  • 《Python程序设计开发宝典》清华大学出版社(2018年2月第3次印刷)

  • 《玩转Python轻松过二级》清华大学出版社(2018年7月第3次印刷)

  • 《Python程序设计基础与应用》机械工业出版社(2018年9月第1次印刷)

董老师127课免费视频地址: https://pan.baidu.com/s/1jJeAs8Q 密码: px59

下期预告:Python批量下载电子邮箱附件+Excel文件多WorkSheets批量合并

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/dongfuguo/article/details/118705812

智能推荐

局域网最少有多少台计算机组成,某实验室准备建立一个由20台计算机组成的局域网,为节约费用,适宜采用通用的( - 问答库..._秦晓珊的博客-程序员宅基地

问题:[单选] 某实验室准备建立一个由20台计算机组成的局域网,为节约费用,适宜采用通用的()技术,A . 以太网B . 令牌环网C . 双总线网络D . ATMWEB组件是WEB开发过程中常用的一个软件单元,有些组件是为了完成一个特定功能而存在于WEB页面或服务器上的,而()不属于WEB组件。 javaapplet。 ASP。 Realpalyer插件。 VB脚本。根据《电子信息系统...

AndroidStudio Viewpger+RadioGroup(引导页)_呵呵哒呵呵哒的博客-程序员宅基地

xmlpackage com.example.day20;import android.support.annotation.NonNull;import android.support.v4.view.PagerAdapter;import android.support.v4.view.ViewPager;import android.support.v7.app.AppCompa...

sparksql与hive整合_杨过悔的博客-程序员宅基地

http://stark-summer.iteye.com/blog/2245286  hive配置编辑 $HIVE_HOME/conf/hive-site.xml,增加如下内容:Prettyprint代码      hive.metastore.uris    thrift://master:9083    Thrift uri f

大学计算机应用技术考试大纲,2019年湖北师范大学914计算机应用技术考研大纲..._名侦探小新的博客-程序员宅基地

2019年湖北师范大学914计算机应用技术考研大纲本站小编 免费考研网/2019-05-292019年全国硕士研究生入学考试湖北师范大学自命题考试科目考试大纲(科目名称:计算机应用技术 科目代码:914)一、 考查目标本科目主要考查考生对当今信息技术的掌握程度,全面考查考生在各专业岗位的计算机应用能力,重点考查考生计算思维能力、计算机软硬件维护能力、使用计算机进行办公自动化信息处理能力、数据库管理...

Spark原理篇之Spark Streaming实现思路与模块概述_听挽风讲大数据的博客-程序员宅基地

1 Spark Streaming概述      和Spark基于RDD的概念相似,Spark Streaming使用离散化流作为抽象表示,叫作DStream。DStream是随着时间推移而收到的数据的序列。在内部,每个时间区间收到的数据都作为RDD的存在,而DStream是由这些RDD所组成的序列(因此得名“离散化”)。DStream...

opencv入门基础学习一_味千爱拉面的博客-程序员宅基地

1.第一章  主要是配置opencv在相应的编程软件里的环境,以及用一个简单的程序测试环境配置是否成功,后续跑了几个简单的程序,图像模糊,图像腐蚀,边缘检测,调用摄像头等来大致了解了一下opencv中的简单图像处理原理:图像腐蚀---用图像的暗色部分腐蚀掉高亮部分(具体原理在图想形态学中才讲);图像模糊---均值滤波;边缘检测---将图像转化为灰度图,再调用blur函数进行降噪;  2.第二章  ...

随便推点

C_learning_notes_string_Sereina的博客-程序员宅基地

learning_notes_stringstrlen 运用所出现的问题strlen 返回值是 size_t,它是一个无符号整型if(strlen(x) >= strlen(y)) 和 if(strlen(x)-strlen(y) >= 0)其实是不等价的,原因是strlen返回值是一个无符号类型,strlen(x)-strlen(y)也是一个无符号类型,而无符号数绝不会是一个负值。当然这个问题也是可以解决的,就是把strlen的返回值强制转换为int类型strlen所计算的字符

ActiveMQ之集群介绍_weixin_34342578的博客-程序员宅基地

ActiveMQ具有强大和灵活的集群功能,ActiveMQ的集群方式主要由两种:Master-Slave和Broker Cluster。一、Master-Slave部署方式Master-Slave方式中,只能是Master提供服务,Slave是实时地备份Master的数据,以保证消息的可靠性。当Master失效时,Slave会自动升级为Master,客户端会自动连接到Slav...

【M29】引用计数_weixin_30655219的博客-程序员宅基地

1、引用计数这项技术,是为了让等值对象对象共享同一实体。此技术的发展有两个动机:a、记录堆上分配的对象,是垃圾回收机制的简单原理;b、节省内存,多个对象具有相同的值,存储多次很笨。速度更快,等值对象避免了对象复制,也就减少了构造和析构。2、考虑,基于引用计数的String,String类中有个StringValue指针,stringValue包含char指针data和引用计数refC...

Web.xml配置详解之context-param_随缘121的博客-程序员宅基地

格式定义:[html] view plaincopycontext-param>  param-name>contextConfigLocationparam-name>  param-value>contextConfigLocationValue>param-value>  context-param>  

微信打开链接被提示已停止访问该网页怎么解决_weixin_45610661的博客-程序员宅基地_微信提示已停止访问该网页应该怎么解决

不管是网站的首页,还是产品的页面地址,以及在线支付的地址,都有可能会被微信提示:已停止访问该网页,据用户投诉及腾讯网址安全中心检测,该网页包含违法或违规内容。为维护绿色上网环境,已停止访问。有的页面甚至还被提示可能是据用户投诉及腾讯网址安全中心检测,该网页可能包含恶意欺诈内容。情况如下图:当出现此种情况后我们应该如何处理呢?我们可以使用VJump工具来实现。可能对于很多商家来说,自主开发耗时耗力...