python中尾递归用法实例详解
作者:feiwen 发布时间:2023-10-09 06:46:15
标签:python,尾递归
本文实例讲述了python中尾递归用法。分享给大家供大家参考。具体分析如下:
如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码。
原理:
当编译器检测到一个函数调用是尾递归的时候,它就覆盖当前的活跃记录而不是在栈中去创建一个新的。编译器可以做到这点,因为递归调用是当前活跃期内最后一条待执行的语句,于是当这个调用返回时栈帧中并没有其他事情可做,因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个,这样所使用的栈空间就大大缩减了,这使得实际的运行效率会变得更高。因此,只要有可能我们就需要将递归函数写成尾递归的形式.
代码:
# This program shows off a python decorator(
# which implements tail call optimization. It
# does this by throwing an exception if it is
# it's own grandparent, and catching such
# exceptions to recall the stack.
import sys
class TailRecurseException:
def __init__(self, args, kwargs):
self.args = args
self.kwargs = kwargs
def tail_call_optimized(g):
"""
This function decorates a function with tail call
optimization. It does this by throwing an exception
if it is it's own grandparent, and catching such
exceptions to fake the tail call optimization.
This function fails if the decorated
function recurses in a non-tail context.
"""
def func(*args, **kwargs):
f = sys._getframe()
if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
raise TailRecurseException(args, kwargs)
else:
while 1:
try:
return g(*args, **kwargs)
except TailRecurseException, e:
args = e.args
kwargs = e.kwargs
func.__doc__ = g.__doc__
return func
@tail_call_optimized
def factorial(n, acc=1):
"calculate a factorial"
if n == 0:
return acc
return factorial(n-1, n*acc)
print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.
@tail_call_optimized
def fib(i, current = 0, next = 1):
if i == 0:
return current
else:
return fib(i - 1, next, current + next)
print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.
希望本文所述对大家的Python程序设计有所帮助。
0
投稿
猜你喜欢
- CSS换肤技术一直是一个比较热门的话题,通过给HTML文档不同的CSS样式应用,实现完全不同或风格迥异的页面效果。这样的技术一直为大家所津津
- 随着3G的普及,越来越多的人使用手机上网。移动设备正超过桌面设备,成为访问互联网的最常见终端。于是,网页设计师不得不面对一个难题:如何才能在
- 由于asp中是使用双引号作为字符串的开始和结束标志的,单一个字符串中的双引号出现次数大于两个时,程序就有可能运行错误。asp中是怎么输出引号
- 1.已知有一个XML文件(bookstore.xml)如下: <?xml version="1.0" e
- 首先,我要在这里写上一些很官方的概念,意在说明面向对象是很具体化的,很实体的模式,不能让有些人看见“对象&rdq
- 首先需要安装Win32-ODBC模块,具体的步骤如下:1:从TOOLS栏目中下载Win32-ODBC.zip,下载完后用winzip解开到一
- 本文实例总结了PHP常用字符串操作函数。分享给大家供大家参考,具体如下:/*常用的字符串输出函数** echo() 输出字符串* print
- 本文只讨论Oracle中最常见的索引,即是B-tree索引。本文中涉及的数据库版本是Oracle8i。 一. 查看系统表中的用户索引 在Or
- 在 MySQL 中,数据库和表对应于那些目录下的目录和文件。因而,操作系统的敏感性决定数据库和表命名的大小写敏感。这就意味着数据库和表名在
- 这段时间,关于asp的前途,关于asp的好坏的讨论贴,都有好些了。当然,大家的心都是好的,但是一些朋友说的话,真是让人郁闷。个人觉得,在现在
- 很多网站在注册时除了需要用户填写用户名与密码之外,还会要求用户输入邮箱,而且是属于那种不填写就不能完成注册的强制型的。碰到这种情况的时候,一
- 如下拉框的text是<input type=button value=ggg>,那么生成的combobox里
- 1 引言在python内存管理中,有一个block的概念。它比较类似于SGI次级空间配置器。首先申请一块大的空间(4KB),然后把它切割成一
- 一、Browser Capabilities组件 该组件最主要的作用是:提取识别客户端浏览器的版本信息。其原理是这样的:当客户端浏览器向服务
- 前端开发中两个很不错的小技巧, CSS三角形与圆角背景. 的确, 它们都可以通过图片来实现, 但, 抛开用代码实现可以减小图片加载量不说,
- 我们有理由相信采用新的内核版本(2.2.16-3 smp)也应该有性能的提升: OS2: Newer minor version kerne
- 微软昨天在其2009年专业开发者大会上展示了下一个版本的Internet Explorer浏览器IE9。尽管只是一个早期版本,IE开发团队还
- 代码如下:<% set studentinstance = CreateStudent()&n
- 1. 吊顶下拉菜单的键盘可用性改进无障碍访问貌似最近比较火,大家都在聊,其中一块就是键盘的可访问性。我们在首页上作了些调整,让用户可以通过键
- 一、实例将以下列表的backup_unit_id全部提取出来示例:dbs = [{ &nbs