algorithm - 如何识别什么是尾递归，什么不是尾递归？

Question

有时候很简单(如果self call是最后一个语句，就是尾递归)，但还是有一些情况让我很困惑。一位教授告诉我“如果自调用之后没有指令执行，那就是尾递归”。这些例子怎么样(忽略它们没有多大意义的事实):

a) 这个应该是尾递归的，看看self-call怎么就是最后一条语句，后面就没有什么可执行的了。

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) 这个怎么样？在这两种情况下， self 调用将是最后执行的事情:

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

因此，前一个函数可能被谈论足够聪明的语言/编译器的人描述为“尾递归”。为该变体用法做好准备。

[*] 存储返回地址、移动堆栈指针和跳转，架构可能会或可能不会将其包裹在单个操作码中，但即使没有，通常也会发生这种情况。