很简单，什么是尾部调用优化?
更具体地说，有哪些小代码段可以应用，哪些地方不可以，并解释原因?
当前回答
TCO (Tail Call Optimization) is the process by which a smart compiler can make a call to a function and take no additional stack space. The only situation in which this happens is if the last instruction executed in a function f is a call to a function g (Note: g can be f). The key here is that f no longer needs stack space - it simply calls g and then returns whatever g would return. In this case the optimization can be made that g just runs and returns whatever value it would have to the thing that called 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
这是因为在这些函数中最后发生的事情是调用另一个函数。
其他回答
尾部调用优化可以避免为函数分配新的堆栈框架，因为调用函数将简单地返回从被调用函数获得的值。最常见的用法是尾部递归，其中为利用尾部调用优化而编写的递归函数可以使用常量堆栈空间。
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)相同的空间。对于非尾部递归事实，情况并非如此，如此大的值可能会导致堆栈溢出。
递归函数方法有一个问题。它建立了一个大小为O(n)的调用堆栈，这使得我们的总内存开销为O(n)。这使得它很容易出现堆栈溢出错误，即调用堆栈变得太大而耗尽空间。
TCO (Tail call optimization)方案。它可以优化递归函数，以避免建立一个庞大的调用堆栈，从而节省内存成本。
有很多语言都在做TCO (JavaScript, Ruby和少数C)，而Python和Java不做TCO。
JavaScript语言已确认使用:)http://2ality.com/2015/06/tail-call-optimization.html
看这里:
http://tratt.net/laurie/tech_articles/articles/tail_call_optimization
你可能知道，递归函数调用会对堆栈造成严重破坏;堆栈空间很容易很快用完。尾部调用优化是一种方法，通过它你可以创建一个使用常量堆栈空间的递归式算法，因此它不会不断增长，你会得到堆栈错误。
在函数式语言中，尾部调用优化就好像函数调用可以返回部分求值的表达式作为结果，然后由调用者求值。
f x = g x
f6变成了g6。因此，如果实现可以返回g6作为结果，然后调用该表达式，它将保存一个堆栈帧。
Also
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;
}
}
}
让我们看一个简单的例子:用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;
}
正如我们在这里看到的，一个足够先进的优化器可以用迭代代替尾递归，这是更有效的，因为您避免了函数调用开销，并且只使用固定数量的堆栈空间。
