什么是尾部调用优化?

What is tail call optimization?

提问人:majelbstoat 提问时间:11/22/2008 最后编辑:Peter Mortensenmajelbstoat 更新时间:10/19/2021 访问量:284572

问:

很简单,什么是尾部调用优化?

更具体地说,有哪些小代码片段可以应用,哪些不能应用,并解释原因?

算法 语言-不可知 尾递归 尾调用优化

评论

20赞 Will Ness 7/18/2016
TCO 将尾部位置的函数调用转换为跳转。

答:

11赞 BobbyShaftoe 11/22/2008 #1

看这里:

http://tratt.net/laurie/tech_articles/articles/tail_call_optimization

您可能知道,递归函数调用可能会对堆栈造成严重破坏;堆栈空间很容易快速用完。尾部调用优化是一种使用恒定堆栈空间的递归样式算法,因此它不会增长和增长,并且会出现堆栈错误。

941赞 Kyle Cronin 11/22/2008 #2

在尾部调用优化中,您可以避免为函数分配新的堆栈帧,因为调用函数将仅返回它从被调用函数获得的值。最常见的用途是尾递归,其中为利用尾调用优化而编写的递归函数可以使用恒定的堆栈空间。

Scheme 是为数不多的在规范中保证任何实现都必须提供这种优化的编程语言之一,因此这里有两个 Scheme 中的阶乘函数示例:

(define (fact x)
  (if (= x 0) 1
      (* x (fact (- x 1)))))

(define (fact x)
  (define (fact-tail x accum)
    (if (= x 0) accum
        (fact-tail (- x 1) (* x accum))))
  (fact-tail x 1))

第一个函数不是尾递归函数,因为当进行递归调用时,函数需要跟踪调用返回后需要对结果执行的乘法操作。因此,堆栈如下所示:

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

相比之下,尾递归因子的堆栈跟踪如下所示:

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

正如你所看到的,我们只需要在每次调用fact-tail时跟踪相同数量的数据,因为我们只是将我们得到的值直接返回到顶部。这意味着即使我调用(事实 1000000),我只需要与(事实 3)相同的空间量。非尾递归事实并非如此,因此较大的值可能会导致堆栈溢出。

评论

132赞 Kyle Cronin 11/23/2008
如果你想了解更多,我建议你阅读《计算机程序的结构和解释》的第一章。
22赞 J D 8/13/2013
严格来说,尾部调用优化不一定会用被调用方替换调用方的堆栈帧,而是确保尾部位置的无限数量的调用只需要有限量的空间。参见 Will Clinger 的论文“Proper tail recursion and space efficiency”:cesura17.net/~will/Professional/Research/Papers/tail.pdf
5赞 dclowd9901 4/26/2016
这只是一种以常量空间方式编写递归函数的方法吗?因为你不能用迭代的方法获得同样的结果吗?
8赞 mcoolive 11/7/2016
@dclowd9901,TCO 允许您更喜欢函数式风格,而不是迭代循环。你可以更喜欢命令式风格。许多语言(Java、Python)不提供 TCO,那么你必须知道函数调用会消耗内存......并且首选命令式风格。
2赞 mbomb007 11/17/2017
应该注意的是,不能保证浏览器对 TCO 的支持,并且可能永远不会支持。stackoverflow.com/a/42788286/2415524
18赞 J Cooper 11/22/2008 #3

请注意,首先,并非所有语言都支持它。

TCO 适用于递归的特殊情况。它的要点是,如果你在函数中做的最后一件事是调用自己(例如,它从“尾部”位置调用自己),编译器可以优化它,使其像迭代而不是标准递归一样。

你看,通常在递归期间,运行时需要跟踪所有递归调用,以便当一个递归调用返回时,它可以在上一次调用时恢复,依此类推。(尝试手动写出递归调用的结果,以直观地了解其工作原理。跟踪所有调用会占用空间,当函数大量调用自身时,空间会变得很重要。但是对于 TCO,它只能说“回到开头,只是这次将参数值更改为这些新值。它可以这样做,因为递归调用之后没有任何内容引用这些值。

评论

6赞 Brian 11/22/2008
尾部调用也可以应用于非递归函数。任何函数在返回前的最后一次计算是对另一个函数的调用,都可以使用尾部调用。
0赞 Steve Gilham 8/7/2009
在逐种语言的基础上不一定正确 - 64 位 C# 编译器可能会插入尾部操作码,而 32 位版本则不会;和 F# 发布版本,但 F# 调试默认不会。
3赞 J D 8/13/2013
“TCO 适用于递归的特殊情况”。恐怕这是完全错误的。尾部调用适用于尾部位置的任何调用。通常在递归的上下文中讨论,但实际上与递归无关。
0赞 NedStarkOfWinterfell 10/9/2014
@Brian,请查看上面提供的链接@btiernay。初始方法尾调用不是经过优化的吗?foo
0赞 Владислав Король 11/10/2022
一个真正伟大的答案,解释了递归的全部意义。简单而低级。
258赞 Claudiu 11/22/2008 #4

TCO(尾部调用优化)是智能编译器可以调用函数并且不占用额外堆栈空间的过程。发生这种情况的唯一情况是,如果在函数 f 中执行的最后一条指令是对函数 g 的调用(注意:g 可以是 f)。这里的关键是 f 不再需要堆栈空间 - 它只是调用 g,然后返回 g 返回的任何内容。在这种情况下,可以进行优化,即 g 只是运行并将它所拥有的任何值返回给称为 f 的东西。

这种优化可以使递归调用占用恒定的堆栈空间,而不是爆炸式增长。

示例:此阶乘函数不可 TCOptimizable:

from dis import dis

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)


dis(fact)
  2           0 LOAD_FAST                0 (n)
              2 LOAD_CONST               1 (0)
              4 COMPARE_OP               2 (==)
              6 POP_JUMP_IF_FALSE       12

  3           8 LOAD_CONST               2 (1)
             10 RETURN_VALUE

  4     >>   12 LOAD_FAST                0 (n)
             14 LOAD_GLOBAL              0 (fact)
             16 LOAD_FAST                0 (n)
             18 LOAD_CONST               2 (1)
             20 BINARY_SUBTRACT
             22 CALL_FUNCTION            1
             24 BINARY_MULTIPLY
             26 RETURN_VALUE

此函数除了在其 return 语句中调用另一个函数外,还会执行其他操作。

以下函数是 TCOptimizable:

def fact_h(n, acc):
    if n == 0:
        return acc
    return fact_h(n-1, acc*n)

def fact(n):
    return fact_h(n, 1)


dis(fact)
  2           0 LOAD_GLOBAL              0 (fact_h)
              2 LOAD_FAST                0 (n)
              4 LOAD_CONST               1 (1)
              6 CALL_FUNCTION            2
              8 RETURN_VALUE

这是因为在这些函数中,最后发生的就是调用另一个函数。

评论

3赞 majelbstoat 11/22/2008
整个“函数 g 可以是 f”的事情有点令人困惑,但我明白你的意思,这些例子确实澄清了事情。多谢!
19赞 rmcc 11/8/2012
说明这个概念的优秀例子。只要考虑到您选择的语言必须实现尾部调用消除或尾部调用优化。在用 Python 编写的示例中,如果输入值 1000,则会收到“RuntimeError: maximum recursion depth exceeded”,因为默认的 Python 实现不支持尾递归消除。请看 Guido 本人的帖子,解释为什么会这样:neopythonic.blogspot.pt/2009/04/tail-recursion-elimination.html
0赞 Will Ness 9/21/2016
唯一的情况”有点太绝对了;还有TRMC,至少在理论上,它会以同样的方式优化或处于尾部位置。(cons a (foo b))(+ c (bar d))
0赞 Nithin 10/5/2017
我更喜欢你的 f 和 g 方法,而不是公认的答案,也许是因为我是一个数学人。
0赞 Jacques Mathieu 12/1/2017
我想你的意思是 TCOptimized。说它不是 TCOptimizable 意味着它永远无法优化(实际上可以)
704赞 Christoph 3/22/2012 #5

让我们看一个简单的例子:用 C 语言实现的阶乘函数。

我们从明显的递归定义开始

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    return n * fac(n - 1);
}

如果函数返回前的最后一个操作是另一个函数调用,则函数以尾部调用结束。如果此调用调用相同的函数,则它是尾递归的。

尽管乍一看是尾递归的,但事实并非如此fac()

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    unsigned acc = fac(n - 1);
    return n * acc;
}

即最后一个操作是乘法而不是函数调用。

但是,可以通过将累积值作为附加参数向下传递调用链,并仅将最终结果作为返回值再次传递来重写为尾递归:fac()

unsigned fac(unsigned n)
{
    return fac_tailrec(1, n);
}

unsigned fac_tailrec(unsigned acc, unsigned n)
{
    if (n < 2) return acc;
    return fac_tailrec(n * acc, n - 1);
}

现在,为什么这很有用?因为我们在尾部调用后立即返回,所以我们可以在尾部位置调用函数之前丢弃之前的堆栈帧,或者,在递归函数的情况下,按原样重用堆栈帧。

尾部调用优化将我们的递归代码转换为

unsigned fac_tailrec(unsigned acc, unsigned n)
{
TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

这可以内联到我们到达fac()

unsigned fac(unsigned n)
{
    unsigned acc = 1;

TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

这相当于

unsigned fac(unsigned n)
{
    unsigned acc = 1;

    for (; n > 1; --n)
        acc *= n;

    return acc;
}

正如我们在这里看到的,一个足够高级的优化器可以用迭代来代替尾递归,这要高效得多,因为你避免了函数调用开销,只使用恒定的堆栈空间。

评论

0赞 Shasak 11/5/2015
您能解释一下 stackframe 的确切含义吗?调用堆栈和堆栈帧之间有区别吗?
16赞 Christoph 11/6/2015
@Kasahs:堆栈帧是调用堆栈中“属于”给定(活动)函数的部分;cf en.wikipedia.org/wiki/Call_stack#Structure
2赞 agm1984 11/13/2017
读完这篇文章后,我才有相当强烈的顿悟 2ality.com/2015/06/tail-call-optimization.html
2赞 Jose Quinteiro 6/11/2020
不错的 C 迭代示例
0赞 JenyaKh 3/6/2023
谢谢。我觉得你的解释最容易理解。
3赞 grillSandwich 8/20/2012 #6
  1. 我们应该确保函数本身没有 goto 语句。由于函数调用是被调用方函数中的最后一件事。

  2. 大规模递归可以使用它来进行优化,但在小规模下,使函数调用尾部调用的指令开销会降低实际目的。

  3. TCO 可能会导致函数永远运行:

    void eternity()
    {
        eternity();
    }
    

评论

0赞 nomen 3/23/2013
3 尚未优化。这是编译器转换为迭代代码的未优化表示,迭代代码使用常量堆栈空间而不是递归代码。TCO 不是对数据结构使用错误递归方案的原因。
0赞 grillSandwich 3/24/2013
“TCO 不是对数据结构使用错误递归方案的原因” 请详细说明这与给定案例的关系。上面的示例仅指出了在调用堆栈上分配帧的示例,无论是否具有 TCO。
0赞 nomen 3/25/2013
您选择使用毫无根据的递归来遍历 ()。这与TCO无关。永恒恰好是尾叫位置,但尾叫位置不是必需的: void eternity() { eternity();
0赞 nomen 3/26/2013
当我们在做的时候,什么是“大规模递归”?为什么我们应该避免在函数中使用 goto?这既不是必要的,也不足以允许 TCO。什么指令开销?TCO 的全部意义在于,编译器将尾部位置的函数调用替换为 goto。
0赞 grillSandwich 3/27/2013
TCO 是关于优化调用堆栈上使用的空间。我所说的大规模递归是指帧的大小。每次发生递归时,如果我需要在被调用方函数上方分配一个巨大的调用帧堆栈,TCO 会更有帮助,并允许我进行更多级别的递归。但是,如果我的帧大小较小,我可以不使用 TCO,并且仍然可以很好地运行我的程序(我在这里不是在谈论无限递归)。如果函数中只剩下 goto,则“tail”调用实际上不是 tail 调用,并且 TCO 不适用。
78赞 btiernay 8/26/2012 #7

对于尾部调用、递归尾部调用和尾部调用优化,我发现的最好的高级描述可能是博客文章

“到底是什么:尾巴叫”

丹·苏加尔斯基 (Dan Sugalski)。关于尾部调用优化,他写道:

考虑一下这个简单的函数:

sub foo (int a) {
  a += 15;
  return bar(a);
}

那么,你,或者更确切地说,你的语言编译器,能做什么呢?好吧,它能做的是将表单的代码转换为低级序列。在我们的示例中,这意味着在调用 之前,会自行清理,然后,我们不是作为子例程调用,而是对 的开头执行低级操作。已经从堆栈中清除了自己,所以当启动时,它看起来像是调用了谁真的调用了,当返回其值时,它直接将其返回给调用者,而不是将其返回给调用者。return somefunc();pop stack frame; goto somefunc();barfoobargotobarFoobarfoobarbarfoofoo

关于尾递归:

如果函数作为其最后一次操作返回,则会发生尾递归 调用自身的结果。尾递归更容易处理 因为不必跳到一些随机的开头 函数,你只需回到开头 你自己,这是一件非常简单的事情。

所以这个:

sub foo (int a, int b) {
  if (b == 1) {
    return a;
  } else {
    return foo(a*a + a, b - 1);
  }

悄悄地变成了:

sub foo (int a, int b) {
  label:
    if (b == 1) {
      return a;
    } else {
      a = a*a + a;
      b = b - 1;
      goto label;
   }

我喜欢这个描述的地方在于,对于那些来自命令式语言背景(C,C++,Java)的人来说,它是多么简洁和容易掌握

评论

0赞 NedStarkOfWinterfell 10/9/2014
我不明白,初始函数尾调用不是优化了吗?它只是调用一个函数作为其最后一步,它只是返回该值,对吧?foo
0赞 Will Ness 4/8/2015
@Cupidvogel正确的,尽管它不是 TCOptimized,而是 TCOptimizable。
1赞 btiernay 9/10/2015
@TryinHard可能不是你的想法,但我更新了它,给出了它的要点。对不起,不打算重复整篇文章!
2赞 Sevin7 10/25/2015
谢谢,这比投票最多的 scheme 示例更简单、更易于理解(更不用说,Scheme 不是大多数开发人员理解的通用语言)
2赞 James Beninger 12/26/2016
作为一个很少深入研究功能语言的人,看到“我的方言”的解释是令人欣慰的。函数式程序员有一种(可以理解的)倾向,即用他们选择的语言进行传福音,但来自命令式世界,我发现要围绕这样的答案来理解要容易得多。
6赞 Rupesh Kumar Tiwari 7/30/2018 #8

递归函数方法存在问题。它构建了一个大小为 O(n) 的调用堆栈,这使得我们的总内存成本为 O(n)。这使得它容易受到堆栈溢出错误的影响,即调用堆栈变得太大并耗尽空间。

尾部调用优化 (TCO) 方案。它可以优化递归函数,以避免构建高调用堆栈,从而节省内存成本。

有许多语言在做TCO,比如(JavaScript、Ruby和少数C),而Python和Java不做TCO。

JavaScript 语言已确认使用 :)http://2ality.com/2015/06/tail-call-optimization.html

26赞 Ciro Santilli OurBigBook.com 3/19/2019 #9

具有 x86 反汇编分析的 GCC C 最小可运行示例

让我们看看 GCC 如何通过查看生成的程序集来自动为我们进行尾部调用优化。

这将作为其他答案中提到的一个非常具体的例子,例如 https://stackoverflow.com/a/9814654/895245 优化可以将递归函数调用转换为循环。

这反过来又节省了内存并提高了性能,因为内存访问通常是当今使程序变慢的主要因素

作为输入,我们给 GCC 一个基于非优化朴素堆栈的阶乘:

tail_call.c

#include <stdio.h>
#include <stdlib.h>

unsigned factorial(unsigned n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main(int argc, char **argv) {
    int input;
    if (argc > 1) {
        input = strtoul(argv[1], NULL, 0);
    } else {
        input = 5;
    }
    printf("%u\n", factorial(input));
    return EXIT_SUCCESS;
}

GitHub 上游

编译和反汇编:

gcc -O1 -foptimize-sibling-calls -ggdb3 -std=c99 -Wall -Wextra -Wpedantic \
  -o tail_call.out tail_call.c
objdump -d tail_call.out

其中 是尾部调用的泛化名称,根据:-foptimize-sibling-callsman gcc

   -foptimize-sibling-calls
       Optimize sibling and tail recursive calls.

       Enabled at levels -O2, -O3, -Os.

如上所述:如何检查 gcc 是否正在执行尾递归优化?

我选择是因为:-O1

  • 优化不是用 完成的。我怀疑这是因为缺少所需的中间转换。-O0
  • -O3生成不敬虔的高效代码,这些代码不会很有教育意义,尽管它也经过了尾部调用优化。

拆卸方式:-fno-optimize-sibling-calls

0000000000001145 <factorial>:
    1145:       89 f8                   mov    %edi,%eax
    1147:       83 ff 01                cmp    $0x1,%edi
    114a:       74 10                   je     115c <factorial+0x17>
    114c:       53                      push   %rbx
    114d:       89 fb                   mov    %edi,%ebx
    114f:       8d 7f ff                lea    -0x1(%rdi),%edi
    1152:       e8 ee ff ff ff          callq  1145 <factorial>
    1157:       0f af c3                imul   %ebx,%eax
    115a:       5b                      pop    %rbx
    115b:       c3                      retq
    115c:       c3                      retq

跟:-foptimize-sibling-calls

0000000000001145 <factorial>:
    1145:       b8 01 00 00 00          mov    $0x1,%eax
    114a:       83 ff 01                cmp    $0x1,%edi
    114d:       74 0e                   je     115d <factorial+0x18>
    114f:       8d 57 ff                lea    -0x1(%rdi),%edx
    1152:       0f af c7                imul   %edi,%eax
    1155:       89 d7                   mov    %edx,%edi
    1157:       83 fa 01                cmp    $0x1,%edx
    115a:       75 f3                   jne    114f <factorial+0xa>
    115c:       c3                      retq
    115d:       89 f8                   mov    %edi,%eax
    115f:       c3                      retq

两者之间的主要区别在于:

  • uses ,这是典型的非优化函数调用。-fno-optimize-sibling-callscallq

    此指令将返回地址推送到堆栈,从而增加它。

    此外,此版本还执行 ,这会%rbx 推送到堆栈push %rbx

    GCC 之所以这样做,是因为它将第一个函数参数 () 存储到 中,然后调用 。edinebxfactorial

    GCC 需要这样做,因为它正在准备再次调用 ,这将使用新的 .factorialedi == n-1

    它之所以选择,是因为这个寄存器是被调用方保存的:通过 linux x86-64 函数调用保留哪些寄存器,因此子调用不会更改它并丢失。ebxfactorialn

  • 不使用任何推送到堆栈的指令:它只使用指令和 进行跳转。-foptimize-sibling-callsgotofactorialjejne

    因此,此版本等效于 while 循环,无需任何函数调用。堆栈使用率是恒定的。

在 Ubuntu 18.10、GCC 8.2 中测试。

0赞 Peter Driscoll 3/21/2020 #10

在函数式语言中,尾部调用优化就好像函数调用可以返回一个部分计算的表达式作为结果,然后由调用者进行评估。

f x = g x

f 6 减少到 g 6。因此,如果实现可以返回 g 6 作为结果,然后调用该表达式,它将保存堆栈帧。

f x = if c x then g x else h x.

降低到 f 6 到 g 6 或 h 6。因此,如果实现评估 c 6 并发现它是真的,那么它可以减少,

if true then g x else h x ---> g x

f x ---> h x

一个简单的非尾调用优化解释器可能如下所示,

class simple_expresion
{
    ...
public:
    virtual ximple_value *DoEvaluate() const = 0;
};

class simple_value
{
    ...
};

class simple_function : public simple_expresion
{
    ...
private:
    simple_expresion *m_Function;
    simple_expresion *m_Parameter;

public:
    virtual simple_value *DoEvaluate() const
    {
        vector<simple_expresion *> parameterList;
        parameterList->push_back(m_Parameter);
        return m_Function->Call(parameterList);
    }
};

class simple_if : public simple_function
{
private:
    simple_expresion *m_Condition;
    simple_expresion *m_Positive;
    simple_expresion *m_Negative;

public:
    simple_value *DoEvaluate() const
    {
        if (m_Condition.DoEvaluate()->IsTrue())
        {
            return m_Positive.DoEvaluate();
        }
        else
        {
            return m_Negative.DoEvaluate();
        }
    }
}

尾部调用优化解释器可能如下所示,

class tco_expresion
{
    ...
public:
    virtual tco_expresion *DoEvaluate() const = 0;
    virtual bool IsValue()
    {
        return false;
    }
};

class tco_value
{
    ...
public:
    virtual bool IsValue()
    {
        return true;
    }
};

class tco_function : public tco_expresion
{
    ...
private:
    tco_expresion *m_Function;
    tco_expresion *m_Parameter;

public:
    virtual tco_expression *DoEvaluate() const
    {
        vector< tco_expression *> parameterList;
        tco_expression *function = const_cast<SNI_Function *>(this);
        while (!function->IsValue())
        {
            function = function->DoCall(parameterList);
        }
        return function;
    }

    tco_expresion *DoCall(vector<tco_expresion *> &p_ParameterList)
    {
        p_ParameterList.push_back(m_Parameter);
        return m_Function;
    }
};

class tco_if : public tco_function
{
private:
    tco_expresion *m_Condition;
    tco_expresion *m_Positive;
    tco_expresion *m_Negative;

    tco_expresion *DoEvaluate() const
    {
        if (m_Condition.DoEvaluate()->IsTrue())
        {
            return m_Positive;
        }
        else
        {
            return m_Negative;
        }
    }
}