专栏首页Python小屋尾递归优化原理与Python实现(以Fibonacci数列和小明爬楼梯问题为例)

尾递归优化原理与Python实现(以Fibonacci数列和小明爬楼梯问题为例)

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

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

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

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

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

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

还是栈崩溃。。。。

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

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

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

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

运行结果如下:

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

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

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

运行结果如下:

本文分享自微信公众号 - Python小屋(Python_xiaowu),作者:董付国

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-09-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 在Python程序中设置函数最大递归深度

    在函数调用时,为了保证能够正确返回,必须进行保存现场和恢复现场,也就是被调函数结束后能够回到主调函数中离开时的位置然后继续执行主调函数中的代码。这些现场或上下文...

    Python小屋屋主
  • Python+matplotlib实现鼠标跟随的动态距离标注

    封面图片:《Python程序设计基础(第2版)》,ISBN:9787302490562,董付国,清华大学出版社

    Python小屋屋主
  • Python批量下载电子邮件附件并汇总合并Excel文件

    首先,通过查阅资料,了解电子邮件和Excel文件的结构,确定要用到的标准库和扩展库,并进行导入:

    Python小屋屋主
  • Elasticsearch Rest Client实战

    Elasticsearch官方推荐使用Java REST客户端连接集群并进行数据操作。

    bellen
  • JAVA学习中Swing部分JDialog对话框窗体的简单学习

    package com.swing; import java.awt.Color; import java.awt.Container; import jav...

    别先生
  • Objective-C 工厂模式(下) -- 抽象工厂模式

    比如用户要买iPhone就创建一个Apple工厂来生产手机, 要买Android手机就创建一个Goolge工厂

    周希
  • 哈工大硕士生用Python实现了11种数据降维算法,代码已开源!

    网上关于各种降维算法的资料参差不齐,同时大部分不提供源代码。这里有个 GitHub 项目整理了使用 Python 实现了 11 种经典的数据抽取(数据降维)算法...

    AI算法与图像处理
  • 基于 Python 的 11 种经典数据降维算法

    网上关于各种降维算法的资料参差不齐,同时大部分不提供源代码。这里有个 GitHub 项目整理了使用 Python 实现了 11 种经典的数据抽取(数据降维)算法...

    统计学家
  • 哈工大硕士生用 Python 实现了 11 种经典数据降维算法,源代码库已开放

    网上关于各种降维算法的资料参差不齐,同时大部分不提供源代码。这里有个 GitHub 项目整理了使用 Python 实现了 11 种经典的数据抽取(数据降维)算法...

    新智元
  • 基于 Python 的 11 种经典数据降维算法

    网上关于各种降维算法的资料参差不齐,同时大部分不提供源代码。这里有个 GitHub 项目整理了使用 Python 实现了 11 种经典的数据抽取(数据降维)算法...

    石晓文

扫码关注云+社区

领取腾讯云代金券