如何识别什么是尾递归，什么不是尾递归？
有时它很简单（如果 self 调用是最后一个语句，则它是尾递归），但仍然有一些情况让我感到困惑。一位教授告诉我“如果自调用后没有指令执行，那就是尾递归”。这些例子怎么样（忽略它们没有多大意义的事实）：
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) 这个怎么样？在这两种情况下， self 调用将是最后执行的事情：
function foo(n)
{
if(n == 0)
return 0;
else
{
if(n > 100)
return foo(n - 2);
else
return foo(n - 1);
}
}
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);
}
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
它可能会帮助您从尾部调用优化的实际实施方式角度来思考这个问题。当然，这不是定义的一部分，但它确实激发了定义。
通常，当调用函数时，调用代码会将稍后需要的任何寄存器值存储在堆栈上。它还将存储一个返回地址，指示调用后的下一条指令。它将做任何需要做的事情来确保为被调用者正确设置堆栈指针。然后它会跳转到目标地址[*]（在本例中是相同的函数）。返回时，它知道返回值位于调用约定（寄存器或堆栈槽）指定的位置。
对于尾部调用，调用者不会这样做。它忽略任何寄存器值，因为它知道以后不再需要它们。它设置堆栈指针，以便被调用者将使用与调用者相同的堆栈，并且它不会将自己设置为返回地址，它只是跳转到目标地址。因此，被调用者将覆盖相同的堆栈区域，它将其返回值放在调用者放置其返回值的同一位置，并且当它返回时，它不会返回到其调用者，而是返回到其调用者的呼叫者。
因此，非正式地，当有可能发生尾调用优化并且尾调用的目标是函数本身时，函数是尾递归的。效果或多或少与函数包含循环相同，尾部调用不是调用自身，而是跳转到循环的开头。这意味着调用后必须不需要任何变量（实际上没有“要做的工作”，这在像 C++ 这样的语言中意味着没有任何东西可以被破坏），并且尾部调用的返回值必须由调用者返回。
这都是为了简单/琐碎的尾递归。有一些转换可用于进行尚未实现的尾递归，例如引入额外的参数，这些参数存储“最底层”递归级别使用的一些信息，以完成原本需要完成的工作“出路”。例如：
可以由程序员或由足够智能的编译器自动进行尾递归，如下所示：
因此，前一个函数可能会被谈论足够智能的语言/编译器的人描述为“尾递归” 。为这种变体用法做好准备。
[*] 存储返回地址、移动堆栈指针和跳转，可能会也可能不会被架构封装在单个操作码中，但即使不是，这也是通常发生的情况。
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:
can be made tail-recursive, either by the programmer or automatically by a smart enough compiler, like this:
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.
您的所有函数都是尾递归的。
意思是：自调用后，从函数返回，即不再需要执行任何代码，而不是说函数中不再有任何代码行。功能。
All your functions are tail recursive.
means: After the self-call, you return from the function, i.e. no more code has to be executed, and not that there is no more line of code in the function.
是的;我认为你的教授的意思是，在任何路径中，如果最终指令是递归的，那么它就是尾递归。
因此，所有三个示例都是尾递归的。
Yep; I think your professor meant that in any path, if the final instruction is recursive, then it is tail recursion.
So, all three examples are tail-recursive.
所有三个示例都是尾递归。一般来说，如果函数的结果（“return”关键字后面的表达式）是对函数本身的单独调用，则为尾递归。 表达式的最外层不得涉及其他运算符。如果对自身的调用只是表达式的一部分，那么机器必须执行该调用，但随后必须返回到所述表达式的计算，也就是说，它不是在函数执行的尾部，而是在函数执行的中间。一个表达。然而，这不适用于递归调用可能采用的任何参数：那里允许任何东西，包括对其自身的递归调用（例如“return foo(foo(0));”）。当然，对跳转的调用的优化仅适用于外部调用。
All three examples are tail recursive. Generally speaking, it is tail recursion, if the result of the function (the expression following the "return" keyword) is a lone call to the function itself. No other operator must be involved in the outermost level of the expression. If the call to itself is only a part of an expression then the machine must execute the call but then has to return back into the evaluation of said expression, that is, it was not at the tail of the function execution but in the middle of an expression. This however does not apply to any parameters that the recursive call may take: anything is allowed there, including recursive calls to itself (e.g. "return foo(foo(0));"). The optimization of calls to jumps is only possible for the outer call then, of course.