Python尾递归优化实现代码及原理详解

在传统的递归中，典型的模式是，你执行第一个递归调用，然后接着调用下一个递归来计算结果。这种方式中途你是得不到计算结果，知道所有的递归调用都返回。 这样虽然很大程度上简洁了代码编写，但是让人很难它跟高效联系起来。因为随着递归的深入，之前的一些变量需要分配堆栈来保存。

尾递归相对传统递归，其是一种特例。在尾递归中，先执行某部分的计算，然后开始调用递归，所以你可以得到当前的计算结果，而这个结果也将作为参数传入下一次递归。这也就是说函数调用出现在调用者函数的尾部，因为是尾部，所以其有一个优越于传统递归之处在于无需去保存任何局部变量，从内存消耗上，实现节约特性。
下面以递归计算加法的实例来说明：

我们用python实现：

普通递归调用：

def recursion(n):
  if n==1:
    return n
  else:
    return n+recursion(n-1)

调用这个函数recursion（5），编译器会执行：

recursion(5)
5+recursion(4)
5+(4+recursion(3))
5+(4+(3+recursion(2)))
5+(4+(3+(2+recursion(1))))
5+(4+(3+(2+1)))
15

此处编译器会分配递归栈来保存中间结果

下来看尾递归实现：

def tail_recursion(n,total=0):
  if n==0:
    return total
  else:
    return tail_recursion(n-1, total+n)

此时，编译器做的工作：

tail_recursion(5,0)
tail_recursion(4,5)
tail_recursion(3,9)
tail_recursion(2,12)
tail_recursion(1,14)
tail_recursion(0,15)
15

你可以看到当前时刻的计算值作为第二个参数传入下一个递归，使得系统不再需要保留之前计算结果。

尾递归的优势就显而易见了。

但是python本身不支持尾递归（没有对尾递归做优化），而且对递归的次数有限制，当递归深度超过1000时，会抛出异常：

分别执行recursion(998),tail_recursion(998,0)

输出：

498501
498501

没有问题，当调用

recursion(999),tail_recursion(999,0)时，

输出：RuntimeError: maximum recursion depth exceeded

因为递归次数超出了1000

有人对此为Python的尾递归写了一个优化版本，让Python突破递归调用1000次的限制：Tail Call Optimization Decorator (Python recipe)

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Python中使用装饰器来优化尾递归的示例

    尾递归简介 尾递归是函数返回最后一个操作是递归调用,则该函数是尾递归. 递归是线性的比如factorial函数每一次调用都会创建一个新的栈(last-in-first-out)通过不断的压栈,来创建递归, 很容易导致栈的溢出.而尾递归则使用当前栈通过数据覆盖来优化递归函数. 阶乘函数factorial, 通过把计算值传递的方法完成了尾递归.但是python不支出编译器优化尾递归所以当递归多次的话还是会报错(学习用). eg: def factorial(n, x): if n == 0: ret

  • Python进阶之尾递归的用法实例

    作者是一名沉迷于Python无法自拔的蛇友,为提高水平,把Python的重点和有趣的实例发在简书上. 尾递归 如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的.当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归.尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码. (来源于不说人话的某度) 下面是笔者的个人理解:把计算出的值存在函数内部(当然不止尾递归)

  • 详解python使用递归、尾递归、循环三种方式实现斐波那契数列

    在最开始的时候所有的斐波那契代码都是使用递归的方式来写的,递归有很多的缺点,执行效率低下,浪费资源,还有可能会造成栈溢出,而递归的程序的优点也是很明显的,就是结构层次很清晰,易于理解 可以使用循环的方式来取代递归,当然也可以使用尾递归的方式来实现. 尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去.尾递归就是把当前的运算结果(或路

  • Python递归及尾递归优化操作实例分析

    本文实例讲述了Python递归及尾递归优化操作.分享给大家供大家参考,具体如下: 1.递归介绍 递归简而言之就是自己调用自己.使用递归解决问题的核心就是分析出递归的模型,看这个问题能拆分出和自己类似的问题并且有一个递归出口.比如最简单的就5的阶乘,可以把它拆分成5*4!,然后求4!又可以调用自己,这种问题显然可以用递归解决,递归的出口就是求1!,可以直接返回1.用Python实现如下: def fact(n): if n==1: return n return n*fact(n - 1); pr

  • python中尾递归用法实例详解

    本文实例讲述了python中尾递归用法.分享给大家供大家参考.具体分析如下: 如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的.当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归.尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码. 原理: 当编译器检测到一个函数调用是尾递归的时候,它就覆盖当前的活跃记录而不是在栈中去创建一个新的.编译器可以做到这点,因

  • Python尾递归优化实现代码及原理详解

    在传统的递归中,典型的模式是,你执行第一个递归调用,然后接着调用下一个递归来计算结果.这种方式中途你是得不到计算结果,知道所有的递归调用都返回. 这样虽然很大程度上简洁了代码编写,但是让人很难它跟高效联系起来.因为随着递归的深入,之前的一些变量需要分配堆栈来保存. 尾递归相对传统递归,其是一种特例.在尾递归中,先执行某部分的计算,然后开始调用递归,所以你可以得到当前的计算结果,而这个结果也将作为参数传入下一次递归.这也就是说函数调用出现在调用者函数的尾部,因为是尾部,所以其有一个优越于传统递归之

  • Python进阶之import导入机制原理详解

    目录 前言 1. Module组成 1.1 Module 内置全局变量 2. 包package 2.1 实战案例 3.sys.modules.命名空间 3.1 sys.modules 3.2 命名空间 4. 导入 4.1 绝对导入 4.2 相对导入 4.3 单独导入包 5. import运行机制 5.1 标准import,顶部导入 5.2 嵌套import 前言 在Python中,一个.py文件代表一个Module.在Module中可以是任何的符合Python文件格式的Python脚本.了解Mo

  • Python实现屏幕截图的代码及函数详解

    废话不多说,先给大家看下python实现屏幕截图的代码,具体代码如下所述: from selenium import webdriver import time def capture(url, save_fn="capture.png"): browser = webdriver.Firefox() # Get local session of firefox browser.set_window_size(1200, 900) browser.get(url) # Load pag

  • python里 super类的工作原理详解

    super 的工作原理如下: def super(cls, inst): mro = inst.__class__.mro() return mro[mro.index(cls) + 1] 其中,cls 代表类,inst 代表实例,上面的代码做了两件事: 获取 inst 的 MRO 列表 查找 cls 在当前 MRO 列表中的 index, 并返回它的下一个类,即 mro[index + 1] 当你使用 super(cls, inst) 时,Python 会在 inst 的 MRO 列表上搜索

  • Python为何不支持switch语句原理详解

    Python为何不支持switch语句原理详解

    在这篇文章里,我们会聊一聊为什么 Python 决定不支持 switch 语句. 为什么想要聊这个话题呢? 主要是因为 switch 在其它语言中太常见了,而 Python 却不支持,这样的独特性本身就值得关注,而回答这个问题,也能更加看清 Python 在程序设计上的理念,了解 Python 在语法设计中的决策过程. 本文除了会详细分析 PEP-275 和 PEP-3103,还会介绍到 Python 最新的发展动态(PEP-622),即可能要引入的模式匹配(pattern matching)语

  • Python Handler处理器和自定义Opener原理详解

    我们之前一直都在使用的urlopen,这是一个特殊的opener(也就是模块帮我们构建好的). 但是基本的urlopen()方法不支持代理.cookie等其他的HTTP/HTTPS高级功能.所以要支持这些功能: 1.使用相差的Handler处理器来创建特定功能的处理器对象: 2.然后通过urllib.request.build_opener()方法,创建自定义opener对象 3.使用自定义的opener对象,调用open()方法发送请求. 如果程序里所有的请求都使用自定义的opener,可以使

  • Python numpy多维数组实现原理详解

    NumPy(Numerical Python) 是 Python 语言的一个扩展程序库,支持大量的维度数组与矩阵运算,此外也针对数组运算提供大量的数学函数库.今天就针对多维数组展开来写博客numpy其一部分功能如下: 1.ndarray,是具有矢量算术运算且节省空间的多维数组. 2.可以用于对整组的数据快速进行运算的辨准数学函数. 3.能够用于读写磁盘数据的工具以及用于操作系统内存映射的工具. NumPy它本身其实没有提供很高级别的数据分析功能,NumPy之于数值计算特别重要的原因之一,就是因为

  • Python爬虫JSON及JSONPath运行原理详解

    JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式,它使得人们很容易的进行阅读和编写.同时也方便了机器进行解析和生成.适用于进行数据交互的场景,比如网站前台与后台之间的数据交互. JsonPath 是一种信息抽取类库,是从JSON文档中抽取指定信息的工具,提供多种语言实现版本,包括:Javascript, Python, PHP 和 Java. JsonPath 对于 JSON 来说,相当于 XPATH 对于 XML. JsonPath与XPath语法对

  • Python字符串split及rsplit方法原理详解

    1.描述 split()方法通过指定分隔符对字符串进行切片,如果参数num有指定值,则分隔num+1个子字符串,默认分隔符为所有空字符,包括空格.换行(\n).制表符(\t)等 rstrip()方法通过 2.语法 str.split([sep=None][,count=S.count(sep)]) str.rsplit([sep=None][,count=S.count(sep)]) 3.参数 sep -- 可选参数,指定的分隔符,默认为所有的空字符,包括空格.换行(\n).制表符(\t)等 c

  • Python直接赋值及深浅拷贝原理详解

    定义 直接赋值:就是对象的引用(别名) 浅拷贝(copy):拷贝父对象,不拷贝对象内部的子对象 深拷贝(deepcopy):copy模块的deepcopy方法,完全拷贝父对象及其子对象 解释 b = a: 赋值引用,a和b都指向同一个对象 b = a.copy(): 浅拷贝,a和b都是一个独立的对象,但它们的子对象是指向统一对象(是引用) b = copy.deepcopy(a): 深拷贝,a和b完全拷贝了父对象及其子对象,两者是完全独立的 示例 以下是直接赋值.浅拷贝和深拷贝之对比 impor

随机推荐