非常简单，什么是尾调用优化？
更具体地说，有哪些可以应用尾调用优化的小代码片段，在哪些情况下不能应用，以及为什么不能应用？
什么是尾调用优化？
1084
- majelbstoat
2
20TCO将尾位置的函数调用转换为goto，即跳转。 - Will Ness
12这个问题在那个问题被问出来之前整整提出了8年 ;) - majelbstoat
10个回答
940
尾调用优化是指由于调用函数的函数会直接返回被调用函数所得到的值，因此可以避免为函数分配新的栈帧。最常见的应用是尾递归，在利用尾调用优化编写的递归函数中，可以使用恒定的栈空间。
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 记录相同数量的数据，因为我们只是将获取到的值直接返回到顶部。这意味着即使我调用 (fact 1000000)，我所需的空间与 (fact 3) 相同。这在非尾递归的 fact 中并非如此，因此大量的值可能会导致堆栈溢出。
- nobody
10
132如果你想更深入地了解这个问题，我建议阅读《计算机程序的构造和解释》的第一章。 - Kyle Cronin
22严格来说，尾调用优化并不一定会用被调用的函数取代调用者的栈帧，而是确保在尾位置上无限次调用只需要有限的空间。请参考Will Clinger的论文“Proper tail recursion and space efficiency”：http://www.cesura17.net/~will/Professional/Research/Papers/tail.pdf - J D
5这只是一种在常量空间中编写递归函数的方法吗？因为您不能使用迭代方法达到相同的结果吗？ - dclowd9901
8@ dclowd9901，TCO允许您更喜欢函数式编程而不是迭代循环。您可以选择命令式风格。许多语言（如Java、Python）不提供TCO，因此您必须知道函数调用会花费内存...建议选择命令式风格。 - mcoolive
2值得注意的是，浏览器对尾递归优化的支持并不保证，可能永远也不会得到支持。 - mbomb007
显示剩余5条评论
704
让我们通过一个简单的例子来理解：使用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;
}
从这里我们可以看到，一个足够先进的优化器能够用迭代替换尾递归，因为这样更加高效，避免了函数调用开销，并且只使用了恒定的堆栈空间。
- Christoph
5
你能准确地解释一下栈帧是什么吗？调用栈和栈帧之间有区别吗？ - Shasak
16堆栈帧是调用堆栈中属于给定（活动）函数的部分；参见https://en.wikipedia.org/wiki/Call_stack#Structure。 - Christoph
2在阅读了http://2ality.com/2015/06/tail-call-optimization.html之后，我刚刚有了相当强烈的顿悟。 - agm1984
2不错的C语言迭代示例 - Jose Quinteiro
谢谢。我觉得你的解释最易懂了。 - JenyaKh
257
TCO (Tail Call Optimization) 是一种使智能编译器在调用函数时不使用额外堆栈空间的过程。唯一出现这种情况的情形是，如果函数f中最后一条执行的指令是对函数g的调用（注意：g可以是f）。关键在于f不再需要堆栈空间 - 它只是调用g，然后返回g将要返回的任何值。在这种情况下，优化可以使得g直接运行并将其返回值返回给调用f的东西。
这种优化可以使递归调用所需的堆栈空间为常量，而不会爆炸。
例如：这个阶乘函数无法进行TCO优化：
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
这个函数在其返回语句中除了调用另一个函数之外，还会处理其他事情。
下面的函数可以进行尾部调用优化：
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
这是因为这些函数中发生的最后一件事情就是调用另一个函数。
- Claudiu
8
3“整个‘函数 g 可以是函数 f’的概念有点令人困惑，但我明白你的意思了，并且这些例子真正澄清了事情。非常感谢！” - majelbstoat
19一个很好的例子，用来说明这个概念。只需注意选择的语言必须实现尾递归消除或尾递归优化。在此示例中，使用Python编写，如果输入1000的值，会出现“RuntimeError：maximum recursion depth exceeded”错误，因为默认的Python实现不支持尾递归消除。请参阅Guido本人的一篇文章，解释了这是为什么：http://neopythonic.blogspot.pt/2009/04/tail-recursion-elimination.html。 - rmcc
我更喜欢你的f和g方法，而不是被接受的答案，可能是因为我是一个数学人。 - Nithin
这个例子对我来说似乎不正确。第二个fact是一个包装器，只调用做所有工作的fact_n。如果将原则应用于第一个fact：
def fact1_wrapper(n): return fact(n)，dis的输出看起来会很相似（或者反过来：如果第二个fact不会被拆分为两个函数），导致示例无关紧要。 - CristiFati@Claudiu 我有点困惑。在你的非TCOptimizable示例中，它最后做的事情也是调用函数（即乘法）。为什么
multiply(n，fac(n-1)) 不是TCOptimizable，但 fact_h(n-1, acc*n) 是呢？ - Student显示剩余3条评论
78
我发现关于尾调用、递归尾调用和尾调用优化的最好的高级描述是来自一篇名为"What the heck is: A tail call"的博客文章，作者是Dan Sugalski。在谈到尾调用优化时，他写道：
请思考一下这个简单函数：
所以，你或者说你的语言编译器能做什么呢？它能将形如sub foo (int a) { a += 15; return bar(a); }return somefunc();的代码转换成低级别的序列pop stack frame; goto somefunc();。在我们的例子中，这意味着在我们调用bar之前，foo会先清理自己，然后我们不再像调用子程序那样调用bar，而是执行一个低级别的goto操作，回到bar的开头处。因为foo已经清理出了堆栈，所以当bar开始运行时，看起来好像是调用foo的人实际上调用了bar，而且当bar返回它的值时，它直接将其返回给调用foo的人，而不是返回给foo，然后由foo返回给调用它的函数。关于尾递归：
如果一个函数在最后一步操作中返回调用自身的结果，则称为尾递归。尾递归比较容易处理，因为你只需要跳转回到自己的开头，而不是跳转到某个随机函数的开头，这是一个相当简单的事情。
sub foo (int a, int b) {
if (b == 1) {
return a;
} else {
return foo(a*a + a, b - 1);
}
gets quietly turned into:
被静默转换成：
sub foo (int a, int b) {
label:
if (b == 1) {
return a;
} else {
a = a*a + a;
b = b - 1;
goto label;
}
- btiernay
6
我没明白，初始的
foo 函数不是尾调用优化了吗？它只是在最后一步调用一个函数，并简单地返回该值，对吧？ - SexyBeast@Cupidvogel 正确，尽管它不是TC优化的，而是可进行TC优化的。 - Will Ness
虽然这个链接可能回答了问题，但最好在此处包含答案的基本部分并提供参考链接。如果链接页面更改，仅有链接的答案可能会失效。 - TryinHard
1@TryinHard，也许不是你想要的，但我更新了它，以便概括一下它的内容。抱歉，不会重复整篇文章！ - btiernay
2谢谢，这比大多数得票最高的Scheme示例更简单易懂（更不用说，Scheme不是大多数开发人员都能理解的常见语言了）。 - Sevin7
2作为一个很少涉足函数式语言的人，看到“我的方言”中的解释是令人满意的。函数式程序员有一种（可以理解的）倾向，即在他们选择的语言中进行宣传，但从命令式世界来看，我发现像这样的答案更容易理解。 - James Beninger
26
GCC C 带有 x86 反汇编分析的最小可运行示例
让我们通过查看生成的汇编代码来了解 GCC 如何自动进行尾调用优化。
这将作为一个极其具体的例子，展示其他答案中提到的内容（例如https://dev59.com/eXVC5IYBdhLWcg3wYQEp#9814654），即优化可以将递归函数调用转换为循环。
反过来，这节省了内存并提高了性能，因为内存访问通常是导致程序变慢的主要原因。
我们将向 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;
}
编译和反汇编：
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-calls是根据man 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
两者的关键区别是：
-
-fno-optimize-sibling-calls 使用的是典型的未优化函数调用 callq。该指令将返回地址推入堆栈，因此增加了堆栈使用量。此外，该版本还执行了 push %rbx，它将 推送 %rbx 到堆栈中。GCC 这样做是因为它将第一个函数参数（n）即 edi 存储到 ebx 中，然后调用 factorial。GCC 需要这样做是为了准备另一个对 factorial 的调用，该调用将使用新的 edi == n-1。它选择 ebx 是因为该寄存器是被调用方保存的: Linux x86-64 函数调用中哪些寄存器被保留，因此对 factorial 的子调用不会更改它并且不会丢失 n。-
-foptimize-sibling-calls 不使用任何推送到堆栈的指令：它仅在 factorial 内使用 je 和 jne 指令执行 goto 跳转。因此，这个版本等同于一个 while 循环，没有任何函数调用。堆栈使用量是恒定的。在 Ubuntu 18.10、GCC 8.2 中测试通过。
- Ciro Santilli OurBigBook.com
18
首先需要注意的是，并非所有编程语言都支持TCO。
TCO适用于递归的特殊情况。其要点是，如果函数的最后一步是调用自身（例如从“尾部”位置调用自身），编译器可以将其优化为迭代而不是标准的递归。
通常，在递归过程中，运行时需要跟踪所有递归调用，以便在一个返回时可以恢复到前一个调用点等等。（尝试手动写出递归调用的结果以了解其工作原理。）跟踪所有调用需要占用空间，当函数频繁调用自身时，这个空间开销就变得非常大。但是通过TCO，它只需说“回到开头，只是这一次将参数值更改为这些新值。” 这可以实现，因为递归调用后面没有引用这些值。
- J Cooper
5
6尾调用不仅适用于递归函数，也适用于非递归函数。只要在返回之前执行的最后一个计算是对另一个函数的调用，任何函数都可以使用尾调用。 - Brian
在语言层面上并不一定是真的 -- 64位的C#编译器可能会插入尾操作码，而32位版本则不会；F#的发布版本会这样做，但默认情况下F#的调试版本则不会。 - Steve Gilham
3"TCO是递归的一种特殊情况"这句话是完全错误的。尾调用适用于任何处于尾部位置的调用。虽然在递归的上下文中经常讨论，但实际上与递归没有特定关系。 - J D
@Brian，看一下@btiernay上面提供的链接。初始的
foo方法不是尾调用优化吗？ - SexyBeast一个真正伟大的答案，解释了递归的整个要点。简单而低级。 - Владислав Король
11
看这里：
http://tratt.net/laurie/tech_articles/articles/tail_call_optimization
你可能知道，递归函数调用会对堆栈造成严重影响；很容易迅速耗尽堆栈空间。尾递归优化是一种方式，可以创建使用恒定堆栈空间的递归风格算法，因此它不会越来越大而导致堆栈错误。
- BobbyShaftoe
6
递归函数方法存在问题。它会建立一个大小为O(n)的调用堆栈，从而使我们的总内存成本为O(n)。这使得它容易发生堆栈溢出错误，其中调用堆栈变得过大并耗尽空间。
尾调用优化（TCO）方案。它可以优化递归函数以避免建立高调用堆栈，从而节省内存成本。
有许多语言正在执行TCO，如JavaScript、Ruby和少量C，而Python和Java不执行TCO。
JavaScript语言已确认使用了 :) http://2ality.com/2015/06/tail-call-optimization.html
尾调用优化（TCO）方案。它可以优化递归函数以避免建立高调用堆栈，从而节省内存成本。
有许多语言正在执行TCO，如JavaScript、Ruby和少量C，而Python和Java不执行TCO。
JavaScript语言已确认使用了 :) http://2ality.com/2015/06/tail-call-optimization.html
- Rupesh Kumar Tiwari
3
We should ensure that there are no goto statements in the function itself .. taken care by function call being the last thing in the callee function.
Large scale recursions can use this for optimizations, but in small scale, the instruction overhead for making the function call a tail call reduces the actual purpose.
TCO might cause a forever running function:
void eternity() { eternity(); }
- grillSandwich
7
3尚未进行优化。那是编译器转换为使用恒定堆栈空间而不是递归代码的迭代代码的未优化表示。TCO并不是使用错误的数据结构递归方案的原因。 - nomen
"TCO不是使用错误的递归方案导致数据结构问题的原因。请阐述它与给定案例的相关性。上面的例子只是指出了在使用和不使用TCO时调用栈上分配帧的示例。" - grillSandwich
你选择使用没有根据的递归来遍历()。这与TCO无关。永恒恰好处于尾调用位置，但尾调用位置并非必要：void eternity() { eternity(); exit(); } - nomen
顺便问一下，“大规模递归”是什么？为什么我们应该避免在函数中使用goto？这既不必要也不足以实现TCO。还有什么指令开销？TCO的整个重点在于编译器将尾部位置的函数调用替换为goto。 - nomen
TCO 是关于优化调用栈上使用的空间。大规模递归是指帧的大小。每当递归发生时，如果我需要在被调用函数之上分配一个巨大的帧到调用栈上，TCO 将更有帮助并允许我更多层次的递归。但如果我的帧大小较小，我可以不使用 TCO 并且仍然可以正常运行程序（我并未谈论无限递归）。如果函数中出现了 goto，则“尾”调用实际上不是尾调用，并且 TCO 不适用。 - grillSandwich
显示剩余2条评论
0
在函数式编程语言中，尾调用优化就像一个函数调用可以返回一个部分求值的表达式作为结果，然后由调用者进行求值。
一个简单的非尾调用优化解释器可能看起来像这样，
一个尾调用优化解释器可能看起来像这样：
f x = g x
f6 会被简化为 g6。如果实现能够返回 g6 作为结果，然后调用该表达式，它将节省一个堆栈帧。
另外
f x = if c x then g x else h x.
将 f6 简化为 g6 或 h6。因此，如果实现评估 c6 并发现它为真，则可以简化。
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;
}
}
}
- Peter Driscoll
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接