java - Java中的尾/前向递归

Question

我不明白为什么这是前向递归：

int count(int x) {
    if(x<=0) return 0;
    return 1 + count(x - 1);
}

这是一个练习考试的问题，答案是它的前向递归。为什么会这样？我怎么能区分这两者？

Answer 1

打电话给自己后，你正在做一个加法。尾递归意味着绝对没有什么可以在之后

如果您了解实现，就很清楚为什么。

假设我们count第一次调用 from main，即在program counter 0xAAA处。然后它会执行它的大部分方法。我们会说这个堆栈帧对 count 的递归调用是 at 0xBBB。如果你使用尾递归，在调用自身时，它可以将返回地址设置为0xAAA（直接进入调用我的代码）。如果它之后做任何事情，它必须将返回地址设置为0xBBC（加法的地址）。因为它不需要堆栈帧来存储返回地址，所以将递归转换为迭代也容易得多。当count调用自身时，它可以直接跳转到方法的开头。

解决方案（对于简单的例子）是在另一个参数中建立结果：

int count(int x, int res) {
  if(x<=0) return res;
  return count(x - 1, res + 1);
}

注意我们之后什么都不做。

Answer 2

您是否看过这个 SO 问题，tail vs forward recursion？

马修有答案，长篇大论是：

int count(int x) {
  if(x<=0) return 0;
  return 1 + count(x - 1);
}  

可以写成（并扩展为类似的东西）：

int count(int x) {
    if(x<=0) return 0;
    int tmp_result = count(x - 1);
    return 1 + tmp_result; // e.g. recursion is not last
}