如何识别什么是尾部递归？

Question

有时它很简单(如果自调用是最后一个语句,它是尾递归),但仍有一些案例让我感到困惑.一位教授告诉我"如果在自我调用之后没有执行指令,那就是尾递归".这些例子怎么样(忽略它们没有多大意义的事实):

a)这个应该是尾递归的,看看自调用是最后一个语句,并且在它之后没有任何东西可以执行.

function foo(n)
{
    if(n == 0)
        return 0;
    else
        return foo(n-2);
}

b)但是这个怎么样？它应该是一个尾调用,因为如果条件为真,除了它之外什么都不会执行,但它不是最后一个语句？

function foo(n)
{
    if(n != 0)
        return foo(n-2);
    else
        return 0;
}

c)这个怎么样？在这两种情况下,自我调用将是最后执行的事情:

function foo(n)
{
    if(n == 0)
        return 0;
    else    
    {
        if(n > 100)
            return foo(n - 2);
        else
            return foo(n - 1);
    }
}

Answer 1

根据尾部调用优化的实际实现方式,可以帮助您考虑这一点.当然,这不是定义的一部分,但它确实激发了定义.

通常,在调用函数时,调用代码将在堆栈中存储稍后需要的任何寄存器值.它还将存储一个返回地址,指示调用后的下一条指令.它将尽其所能确保为被调用者正确设置堆栈指针.然后它将跳转到目标地址[*](在这种情况下,相同的功能).返回时,它知道返回值在调用约定(寄存器或堆栈槽)指定的位置.

对于尾调用,调用者不会这样做.它会忽略任何寄存器值,因为它知道以后不需要它们.它设置堆栈指针,以便被调用者将使用调用者所执行的相同堆栈,并且它不将自己设置为返回地址,它只是跳转到目标地址.因此,被调用者将覆盖相同的堆栈区域,它将其返回值放在调用者将其返回值放在同一位置,并且当它返回时,它将不会返回其调用者,而是将返回其调用者的呼叫者.

因此,非正式地,当尾部调用优化可能发生时,以及当尾调用的目标是函数本身时,函数是尾递归的.效果或多或少与函数包含循环相同,而不是调用自身,尾调用跳转到循环的开始.这意味着在调用之后必须没有变量(事实上没有"工作要做",在C++这样的语言中意味着什么都不被破坏),并且调用者必须返回尾调用的返回值.

这都是简单/平凡的尾递归.有一些转换可以用来做一些尾递归的东西,例如引入额外的参数,它们存储了一些信息,这些参数存储了"最底层"递归级别所使用的一些信息.出路".例如:

int triangle(int n) {
    if (n == 0) return 0;
    return n + triangle(n-1);
}

可以由程序员或通过足够聪明的编译器自动进行尾递归,如下所示:

int triangle(int n, int accumulator = 0) {
    if (n == 0) return accumulator;
    return triangle(n-1, accumulator + n);
}

因此,前一个函数可能被描述为足够聪明的语言/编译器的人描述为"尾递归".为变体用法做好准备.

[*]存储返回地址,移动堆栈指针和跳转,可能会也可能不会被架构包含在单个操作码中,但即使不是这样,通常会发生什么.

Answer 2

是的; 我认为你的教授意味着在任何路径中,如果最终指令是递归的,那么它就是尾递归.

所以,这三个例子都是尾递归的.

Answer 3

你的所有函数都是尾递归的.

自我通话后没有指令

意思是:在自调用之后,你从函数返回,即不再需要执行代码,而不是函数中没有更多的代码行.