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

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


当前回答

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

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

You see, normally during recursion, the runtime needs to keep track of all the recursive calls, so that when one returns it can resume at the previous call and so on. (Try manually writing out the result of a recursive call to get a visual idea of how this works.) Keeping track of all the calls takes up space, which gets significant when the function calls itself a lot. But with TCO, it can just say "go back to the beginning, only this time change the parameter values to these new ones." It can do that because nothing after the recursive call refers to those values.

其他回答

让我们看一个简单的例子:用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;
}

正如我们在这里看到的,一个足够先进的优化器可以用迭代代替尾递归,这是更有效的,因为您避免了函数调用开销,并且只使用固定数量的堆栈空间。

递归函数方法有一个问题。它建立了一个大小为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

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

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

You see, normally during recursion, the runtime needs to keep track of all the recursive calls, so that when one returns it can resume at the previous call and so on. (Try manually writing out the result of a recursive call to get a visual idea of how this works.) Keeping track of all the calls takes up space, which gets significant when the function calls itself a lot. But with TCO, it can just say "go back to the beginning, only this time change the parameter values to these new ones." It can do that because nothing after the recursive call refers to those values.

在函数式语言中,尾部调用优化就好像函数调用可以返回部分求值的表达式作为结果,然后由调用者求值。

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;
        }
    }
}

我们应该确保函数本身没有goto语句。函数调用是被调用函数的最后一个内容。 大规模递归可以使用它进行优化,但在小规模中,使函数调用成为尾部调用的指令开销降低了实际目的。 TCO可能导致一个永远运行的函数: 空白永恒() { 永恒(); }