本文共 2694 字，大约阅读时间需要 8 分钟。

尾递归

**尾递归的原理：**当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。

换一种说法，尾递归是指，在函数返回的时候，调用自身本身，并且，return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。

def facttail(int n, int res){    if (n < 0)        return 0;    else if(n == 0)        return 1;    else if(n == 1)        return res;    else        return facttail(n - 1, n *res);}

需要注意的是python 不支持尾递归，递归深度超过1000时会报错，故此需要我们做一些处理来解决这个问题。

尾递归优化

通过实现一个 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 sysclass TailRecurseException:    def __init__(self, args, kwargs):        self.args = args        self.kwargs = kwargsdef 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_optimizeddef 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 sysdef 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:, 就捕获当前尾调用函数的参数, 并抛出异常, 从而销毁递归栈并使用捕获的参数手动调用递归函数. 所以递归的过程中始终只存在一个栈帧对象, 达到优化的目的。

关于装饰器的相关知识可以参考这篇博客：

参考文章：

转载地址：https://mtyjkh.blog.csdn.net/article/details/81978887 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！