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

 更新时间:2020-10-10 04:02:16   作者:佚名   我要评论(0)

在传统的递归中,典型的模式是,你执行第一个递归调用,然后接着调用下一个递归来计算结果。这种方式中途你是得不到计算结果,知道所有的递归调用都返回。 这样虽然

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

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

我们用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)

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

您可能感兴趣的文章:
  • Python递归及尾递归优化操作实例分析
  • Python进阶之尾递归的用法实例
  • 详解python使用递归、尾递归、循环三种方式实现斐波那契数列
  • Python中使用装饰器来优化尾递归的示例
  • python中尾递归用法实例详解

相关文章

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

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

    在传统的递归中,典型的模式是,你执行第一个递归调用,然后接着调用下一个递归来计算结果。这种方式中途你是得不到计算结果,知道所有的递归调用都返回。 这样虽然
    2020-10-10
  • Java两种方式实现动态代理

    Java两种方式实现动态代理

    一、JDK动态代理 Java 在 java.lang.reflect 包中有自己的代理支持,该类(Proxy.java)用于动态生成代理类,只需传入目标接口、目标接口的类加载器以及 Invocation
    2020-10-10
  • Python判断变量是否是None写法代码实例

    Python判断变量是否是None写法代码实例

    代码中经常会有变量是否为None的判断,有三种主要的写法: 第一种是`if x is None`; 第二种是 `if not x:`; 第三种是`if not x is None`(这句这样理解更
    2020-10-10
  • java 枚举enum的用法(与在switch中的用法)

    java 枚举enum的用法(与在switch中的用法)

    实际开发中,很多人可能很少用枚举类型。更多的可能使用常量的方式代替。但枚举比起常量来说,含义更清晰,更容易理解,结构上也更加紧密。看其他人的博文都很详细,
    2020-10-10
  • Python批量获取并保存手机号归属地和运营商的示例

    Python批量获取并保存手机号归属地和运营商的示例

    从Excel读取一组手机号码,批量查询该手机号码的运营商和归属地,并将其追加到该记录的末尾。 import requests import json import xlrd from xlutils.copy impor
    2020-10-10
  • Python特殊属性property原理及使用方法解析

    Python特殊属性property原理及使用方法解析

    1 什么是特性property property是一种特殊的属性,访问它时会执行一段功能(函数)然后返回值 import math class Circle: def __init__(self,radius): #圆的半径
    2020-10-10
  • Python类绑定方法及非绑定方法实例解析

    Python类绑定方法及非绑定方法实例解析

    一、绑定方法   1.对象的绑定方法   首先我们明确一个知识点,凡是类中的方法或函数,默认情况下都是绑定给对象使用的。下面,我们通过实例,来慢慢解析绑
    2020-10-10
  • 在.NET中使用DiagnosticSource的方法

    在.NET中使用DiagnosticSource的方法

    前言 DiagnosticSource是一个非常有意思的且非常有用的API,对于这些API它们允许不同的库发送命名事件,并且它们也允许应用程序订阅这些事件并处理它们,它使我们
    2020-10-07
  • ASP.NET Core 实现基本认证的示例代码

    ASP.NET Core 实现基本认证的示例代码

    HTTP基本认证 在HTTP中,HTTP基本认证(Basic Authentication)是一种允许网页浏览器或其他客户端程序以(用户名:口令) 请求资源的身份验证方式,不要求cookie,sess
    2020-10-07
  • 9个JavaScript日常开发小技巧

    9个JavaScript日常开发小技巧

    1.生成指定范围的数字 在某些情况下,我们会创建一个处在两个数之间的数组。假设我们要判断某人的生日是否在某个范围的年份内,那么下面是实现它的一个很简单的方法
    2020-10-07

最新评论