如何识别什么是尾递归？

一尘不染

如何识别什么是尾递归？

algorithm

有时它很简单（如果self调用是最后一条语句，则是尾部递归），但是仍然有一些情况使我感到困惑。一位教授告诉我，“如果自调用后没有任何指令可以执行，那就是尾递归”。这些示例怎么样（忽略它们没有多大意义的事实）：

a）这个应该是尾递归的，看看自调用是最后一条语句如何，并且在此之后没有什么可执行的。

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

b）但是这个呢？它应该是一个尾部调用，因为如果条件为true，则除了将执行该条件外，什么都不会执行，但这不是最后一条语句吗？

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

阅读 299

2020-07-28

共1个答案

一尘不染

它可能会帮助您从实际实现尾部呼叫优化的角度来考虑这一点。当然，这不是定义的一部分，但确实可以激发定义。

通常，在调用函数时，调用代码会将以后需要的所有寄存器值存储在堆栈中。它还将存储一个返回地址，指示调用后的下一条指令。它会做任何需要做的事情，以确保为被调用者正确设置了堆栈指针。然后它将跳转到目标地址[*]（在这种情况下，是相同的功能）。返回时，它知道返回值在调用约定指定的位置（寄存器或堆栈插槽）。

对于尾部呼叫，呼叫者不执行此操作。它忽略任何寄存器值，因为它知道以后将不需要它们。它设置了堆栈指针，以便被调用者将使用与调用者相同的堆栈，并且不将自身设置为返回地址，它只是跳转到目标地址。因此，被调用方将覆盖相同的堆栈区域，将其返回值放在调用方应将其返回值放在的相同位置，并且当它返回时，将不返回到其调用方，而是返回到其调用方的呼叫者。

因此，非正式地，当可能进行尾部调用优化时，并且当尾部调用的目标是函数本身时，该函数是尾部递归的。效果与该函数包含一个循环大致相同，并且tail调用跳转到循环的开始，而不是调用自身。这意味着在调用之后必须没有任何变量（实际上也不需要“要做的工作”，在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);
}

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

[*]存储返回地址，移动堆栈指针并跳转，可能会也可能不会被体系结构包装在单个操作码中，但是即使这样通常也不会发生。

2020-07-28