详解Python如何实现尾递归优化
作者:misakar 发布时间:2023-11-13 04:20:06
尾递归是一种特殊的递归形式,它在递归调用时不会产生新的栈帧,从而避免了栈溢出的问题。Python并没有对尾递归进行优化,但我们可以通过一些技巧来实现递归优化。本文将详细介绍Python如何实现尾递归优化,并提供两个示例来说明它的用法。
什么是尾递归
在介绍如何实现尾递归优化之前,我们先来了解一下什么是尾递归。
递归是指递归函数在调用自身之后,不再有其他操作,直接返回结果。这种形式的递归可以被优化为迭代形式,从而避免了栈溢出的问题。
例如,下面是一个阶乘函数的递归实现:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
这个函数不是尾递归,因为在递归调用之后还有其他操作(乘法)。如果我们将其改写为尾递归形式,可以得到下代码:
def factorial, acc=1):
if n == 0:
return acc
else:
return factorial(n-1, acc*n)
在这个函数中,我们引入了一个额外的参数acc,用于保存中间结果。在递归调用时,我们将中结果乘以当前的n,并将结果传递给下一次递归调用。当递归到n=0时,我们直接返回中间结果``,从而避免了栈溢出的问题。
如何实现尾递归优化
Python并没有对尾递归进行优化,但我们可以通过一些技巧来实现尾递归优化。具体来,我们可以使用循环、函数参数等方式来避免递归调用产生新的栈帧。
使用循环
使用循环是一种常见的实现尾递归优化的方式。例如,下面是一个使用循环实现阶乘函数的代码:
def factorial(n):
acc = 1
while n > 0:
acc *= n
n -= 1
return acc
在这个函数中,我们使用循环来计算阶乘,避免了递归调用产生新的栈帧。
使用函数参数
使用函数参数也是一种实现尾递归优化的方式。例如,下面是一个使用函数参数实现阶乘函数的代码:
def factorial(n, acc=1):
if n == 0:
return acc
else:
return factorial(n-1, acc*n)
在这个函数中,我们引入了一个额外的参数acc,用于保存中间结果。在递归调用时,我们将中间结果乘以当前的参数n,并将结果传递给下次递归调用。当递归到n=0时,我们直接返回中间结果acc从而避免了栈溢出的问题。
示例1:使用循环实现斐波那契数列
下面是一个使用循环实现斐波那契数列的示例:
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
a, b = 0, 1
for i in range(n-1):
a, b = b, a+b
return b
在这个函数中,我们使用循环来计算斐波那契数列的第n项,避免了递归调用产生新的栈帧。
示例2:使用函数参数实现尾递归优化
下面是一个使用函数参数实现尾递归优化的阶乘函数的示例:
def factorial(n, acc=1):
if n == 0:
return acc
else:
return factorial(n-1, acc*n)
在这个函数中,我们引入了一个额外的参数acc,用于保存中间结果。在递归调用时,我们将中间结果乘以当前的参数n,并将结果传递给下一次递调用。当递归到=0时,我们直接返回中间结果acc,从而避免了栈溢出的问题。
一般递归与尾递归
一般递归
def normal_recursion(n):
if n == 1:
return 1
else:
return n + normal_recursion(n-1)
执行:
normal_recursion(5)
5 + normal_recursion(4)
5 + 4 + normal_recursion(3)
5 + 4 + 3 + normal_recursion(2)
5 + 4 + 3 + 2 + normal_recursion(1)
5 + 4 + 3 + 3
5 + 4 + 6
5 + 10
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
可以看到, 尾递归每一级递归函数的调用变成"线性"的形式. 这时, 我们可以思考, 虽然尾递归调用也会创建新的栈, 但是我们可以优化使得尾递归的每一级调用共用一个栈!, 如此便可解决爆栈和递归深度限制的问题!
C中尾递归的优化
gcc使用-O2
参数开启尾递归优化:
int tail_recursion(int n, int total) {
if (n == 0) {
return total;
}
else {
return tail_recursion(n-1, total+n);
}
}
int main(void) {
int total = 0, n = 4;
tail_recursion(n, total);
return 0;
}
反汇编
$ gcc -S tail_recursion.c -o normal_recursion.S
$ gcc -S -O2 tail_recursion.c -o tail_recursion.S gcc开启尾递归优化
对比反汇编代码如下(AT&T语法, 左图为优化后)
可以看到, 开启尾递归优化前, 使用call调用函数, 创建了新的调用栈(LBB0_3); 而开启尾递归优化后, 就没有新的调用栈生成了, 而是直接pop bp指向的_tail_recursion函数的地址(pushq %rbp)然后返回, 仍旧用的是同一个调用栈!
Python开启尾递归优化
cpython本身不支持尾递归优化, 但是一个牛人想出的解决办法:实现一个 tail_call_optimized 装饰器
#!/usr/bin/env python2.4
# 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)
这里解释一下sys._getframe()
函数:
sys._getframe([depth]):Return a frame object from the call stack.
If optional integer depth is given, return the frame object that many calls below the top of the stack.
If that is deeper than the call stack, ValueEfror is raised. The default for depth is zero,
returning the frame at the top of the call stack.
即返回depth深度调用的栈帧对象.
import sys
def get_cur_info():
print sys._getframe().f_code.co_filename # 当前文件名
print sys._getframe().f_code.co_name # 当前函数名
print sys._getframe().f_lineno # 当前行号
print sys._getframe().f_back # 调用者的帧
说一下tail_call_optimized实现尾递归优化的原理: 当递归函数被该装饰器修饰后, 递归调用在装饰器while循环内部进行, 每当产生新的递归调用栈帧时: f.f_back.f_back.f_code == f.f_code:
, 就捕获当前尾调用函数的参数, 并抛出异常, 从而销毁递归栈并使用捕获的参数手动调用递归函数. 所以递归的过程中始终只存在一个栈帧对象, 达到优化的目的.
为了更清晰的展示开启尾递归优化前、后调用栈的变化和tail_call_optimized装饰器抛异常退出递归调用栈的作用, 我这里利用pudb调试工具做了动图:
开启尾递归优化前的调用
开启尾递归优化后(tail_call_optimized装饰器)的调用
通过pudb右边栏的stack, 可以很清晰的看到调用栈的变化.
因为实现了尾递归优化, 所以factorial(10000)都不害怕递归深度限制报错啦!
来源:https://segmentfault.com/a/1190000007641519
猜你喜欢
- 下面发一个简单的在线调试服务端js代码的asp源码。并可以提示代码具体错误信息。<%@language="javascrip
- 概 述 现在有不少介绍利用ASP实现动态分页的文章,方法大同小异,就是每次利用ADO返回原始数据满足条件记录集中的指定
- icon可以用多个软件制作,也可以通过一些网站把普通图片转换为.ico文件,但通常存在的问题是图片本该透明的地方经转换后变为了黑色或者白色,
- 之前说过要聊聊 干职业设计经理的活 的问题,貌似有些朋友对这个事情还挺关心的,我理解为一方面是掌握对付猎头时候的标准答案,一方面是
- 管理SQL Server内在的帐户和密码时,我们很容易认为这一切都相当的安全。但实际上并非如此。在这里,我们列出了一些对于SQL Serve
- 本文实例总结了PHP session会话操作技巧。分享给大家供大家参考,具体如下:会话技术session将会话数据存储与服务器端,同时使会话
- 本文实例讲述了Python运维自动化之nginx配置文件对比操作。分享给大家供大家参考,具体如下:文件差异对比diff.py#!/usr/b
- A.动态页面第一步:创建转向控制页面,创建网站默认的首页文件(通常为"index.asp"或"default.
- 本文实例为大家分享了微信小程序上传图片到php服务器的具体代码,供大家参考,具体内容如下js代码如下 submitPhoto(){ var
- 如果查询结果很多,服务器解释你的ASP script将花费大量的时间,因为有许多的Response.Write语句要处理. 如果你将输出的全
- 上篇文章讲了js中的传值和传址 和 函数的作用域.这章我们来探讨js中的变量,表达式,和运算符 还有一些 js 语句。升级中……1, 表达式
- 代码'########### '检测远程文件是否存在 '########### function CheckURL(
- Yoho, 大家好,又是我哟~ 首先抱歉让大家等了这么多时间。最近实在比较繁忙啦。不过我还是会尽量抽空出来给大家讲点有的没的,欢迎大家继续
- 第三章 XML的术语提纲:导言 一.XML文档的有关术语 二.DTD的有关术语导言初学XML最令人头疼的就是有一大堆新的术语概念要理解。由于
- Dreamweaver 2004 除了可以插入 Flash SWF 動畫、Flash 文字和 Flash 按鈕以外,這次又新增加了一個叫做
- 大家做网站,特别是自己写的代码,常常担心被一些黑客入侵服务器,从而导致网站代码被盗,给自己带来一些损失。那么我们怎么样做,就算黑客盗了你的代
- 一、备份数据库1、打开SQL企业管理器,在控制台根目录中依次点开Microsoft SQL Server2、SQL Server组-->
- 如果你正在运行使用MySQL的Web应用程序,那么你把密码或者其他敏感信息保存在应用程序里的机会就很大。保护这些数据免受黑客或者窥探者的获取
- PHP quotemeta() 函数实例在预定义的字符前添加反斜杠:<?php$str = "Hello world. (c
- 说到排序,我想起一个故事,大意是说唐僧师徒西游美利坚,孙悟空买了本词典,开始逐条背诵单词。他们第一次下美国馆子的时候,不管服务员推荐什么,孙