由网友(霹雳搅屎棍)分享简介：有时候它很简单（如果自调用的最后一条语句，它的尾递归），但仍然有一些让我困惑的情况。一位教授告诉我，如果没有指令自呼后执行，它的尾递归。如何对这些例子（忽视的事实，他们没有多大意义）：a）本应该是尾递归，眼看着自呼又是怎样的最后一条语句，并没有什么离开后执行。函数foo（N）{如果（N == 0）返回0;其他返回fo...

有时候它很简单（如果自调用的最后一条语句，它的尾递归），但仍然有一些让我困惑的情况。一位教授告诉我，如果没有指令自呼后执行，它的尾递归。如何对这些例子（忽视的事实，他们没有多大意义）：

a）本应该是尾递归，眼看着自呼又是怎样的最后一条语句，并没有什么离开后执行。

 函数foo（N）
{
    如果（N == 0）
        返回0;
    其他
        返回foo的第（n-2）;
}
 

二）但是，这个怎么样呢？这应该是一个尾调用，因为如果条件为真，那么除了它会被执行，但它不是最后的声明？

 函数foo（N）
{
    如果（N！= 0）
        返回foo的第（n-2）;
    其他
        返回0;
}
 

C）这条怎么样？在这两种情况下，自己的呼叫将是最后的事情执行的：

 函数foo（N）
{
    如果（N == 0）
        返回0;
    其他
    {
        如果（正→100）
            返回FOO（N  -  2）;
        其他
            返回FOO（N  -  1）;
    }
}
 

解决方案

它可以帮助你思考这个在尾部调用的优化实际上是如何实现的条款。这当然不是定义的一部分，但它确实激励定义

通常情况下，当一个函数被调用，调用code将存储，这将在以后需要，在栈上的任何寄存器值。它也将存储的返回地址，指示呼叫之后的下一条指令。它会做任何事需要做，以确保堆栈指针正确设置为被叫方。然后，将跳转到目标地址[*]（在此情况下，同样的功能）。在返回时，它知道返回的值是通过调用约定（寄存器或栈槽）指定的地方。

有关尾调用，调用者没有做到这一点。它忽略任何寄存器的值，因为它知道它会不会以后需要它们。它设置堆栈指针，以便被叫将使用相同​​的堆栈呼叫者做的，它不设置本身起来作为返回地址，这只是跳转到目标地址。因此，被叫方将覆盖相同的堆栈区域，它将把它的返回值在相同的位置，该呼叫者将投入其返回值，并且当它返回，它不会返回到它的调用者，但将返回到其调用者的调用者。

因此​​，非正式的，功能是尾递归的时候它有可能为一尾调用优化的发生，而当尾调用的目标函数本身。效果或多或少相同，如果函数包含的一个环，和而不是调用自身时，尾巴呼叫跳转到循环的开始。这意味着必须有没有电话（实际上没有工作要做，这在像C ++语言意味着什么被析构）后所需的变量，而尾部调用的返回值必须由调用者返回。

这是所有简单/平凡尾递归。有变换，可用于使一些尾递归这是没有准备好，例如引入额外的参数，存储所用递归的最底下电平的一些信息，这样做，否则将完成的工作的出路。因此，例如：

  INT三角形（INT N）{
    如果（N == 0）返回0;
    返回N +三角形（N-1）;
}
 

可尾递归的，无论是由程序员或自动通过一个足够聪明的编译器，像这样的：

  INT三角形（INT N，INT累加器= 0）{
    如果（N == 0）收益累加;
    返回三角形（n-1个，累加器+ N）;
}
 

因此​​，前者的功能可能会被别人谁在谈论一个足够聪明的语言/编译器描述为尾递归。被prepared该变种使用。

[*]保存一个返回地址，移动堆栈指针，和跳跃，可以或可以不被包裹在一个单个运算code。通过该结构，但即使不这通常会发生什么。

Sometimes it's simple enough (if the self call is the last statement, it's tail recursion), but there are still cases that confuse me. A professor told me that "if there's no instruction to execute after the self-call, it's tail recursion". How about these examples (disregard the fact that they don't make much sense) :

a) This one should be tail recursive, seeing how the self-call is the last statement, and there's nothing left to execute after it.

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

b) But how about this one? It should be a tail call, because if the condition is true, nothing except it will be executed, but it's not the last statement?

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

c) How about this one? In both cases, the self call will be the last thing executed :

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

解决方案

It might help you to think about this in terms of how tail-call optimisations are actually implemented. That's not part of the definition, of course, but it does motivate the definition.

Typically when a function is called, the calling code will store any register values that it will need later, on the stack. It will also store a return address, indicating the next instruction after the call. It will do whatever it needs to do to ensure that the stack pointer is set up correctly for the callee. Then it will jump to the target address[*] (in this case, the same function). On return, it knows the return value is in the place specified by the calling convention (register or stack slot).

For a tail call, the caller doesn't do this. It ignores any register values, because it knows it won't need them later. It sets up the stack pointer so that the callee will use the same stack the caller did, and it doesn't set itself up as the return address, it just jumps to the target address. Thus, the callee will overwrite the same stack region, it will put its return value in the same location that the caller would have put its return value, and when it returns, it will not return to its caller, but will return to its caller's caller.

Therefore, informally, a function is tail-recursive when it is possible for a tail call optimisation to occur, and when the target of the tail call is the function itself. The effect is more or less the same as if the function contained a loop, and instead of calling itself, the tail call jumps to the start of the loop. This means there must be no variables needed after the call (and indeed no "work to do", which in a language like C++ means nothing to be destructed), and the return value of the tail call must be returned by the caller.

This is all for simple/trivial tail-recursion. There are transformations that can be used to make something tail-recursive which isn't already, for example introducing extra parameters, that store some information used by the "bottom-most" level of recursion, to do work that would otherwise be done on the "way out". So for instance:

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

can be made tail-recursive, either by the programmer or automatically by a smart enough compiler, like this:

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

Therefore, the former function might be described as "tail recursive" by someone who's talking about a smart enough language/compiler. Be prepared for that variant usage.

[*] Storing a return address, moving the stack pointer, and jumping, may or may not be wrapped up in a single opcode by the architecture, but even if not that's typically what happens.