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

有时它很简单（如果自我调用是最后一个语句，它是尾递归），但仍有一些情况令我困惑。一位教授告诉我，“如果在自助之后没有执行的指令，那就是尾递归”。这些例子如何（忽略它们没有多大意义的事实）：如何识别什么是，什么不是尾递归？

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

来源

2010-09-09 fingerprint211b

它可能会帮助你考虑如何实际实现tail-call优化。当然，这不是定义的一部分，但它确实激发了定义。

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

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

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

因此，前者的功能可以被描述为“尾巴递归“的人正在谈论一个足够聪明的语言/编译器。准备好这一变体使用。存储返回地址，移动堆栈指针和跳转，可能会或不可能被体系结构封装在单个操作码中，但即使不是这通常会发生什么情况。

来源

2010-09-09 18:22:32

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

所以，这三个例子都是尾递归的。

来源

2010-09-09 16:36:30 Vermiscious

所有的函数都是尾递归的。

没有指令后留下的自呼

是指：自呼后，您从功能返回，即没有更多的代码已被执行，而不是有函数中没有更多的代码行。

来源

2010-09-09 16:36:49 Dario

这三个例子都是尾递归的。一般来说，如果函数的结果（“return”关键字后面的表达式）是对函数本身的单独调用，则它是尾递归。 没有其他操作员必须参与表达式的最外层。如果对自身的调用只是表达式的一部分，那么机器必须执行调用，但必须返回到对所述表达式的评估中，也就是说，它不在函数执行的尾部，而是在一种表达。然而，这不适用于递归调用可能采用的任何参数：在那里允许任何事物，包括对其自身的递归调用（例如“return foo（foo（0））;”）。当然，优化跳转调用仅适用于外部调用。

来源

2010-09-09 16:52:21 slartibartfast

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

回答

相关问题