Java中的尾递归/头递归

Question

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

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

这是一道实践考试中的问题，答案是它是正向递归。为什么会是这样呢？我应该如何区分这两种情况呢？

- Snowman

---

练习题目第2部分 - 如何使其成为尾递归？ - jon_darkstar

可能是尾递归与前向递归的重复问题。 - user177800

Answer 1

你在调用自己后进行加法操作。尾递归意味着绝对不能有任何操作在其后面。

如果你理解了实现，这就很清楚了。

比如我们第一次从main中调用count，它位于程序计数器 0xAAA处。然后它执行大部分方法。我们会说此堆栈帧的递归调用到count是在0xBBB处。如果你使用尾递归，在调用自身时，它可以将返回地址设置为0xAAA(直接转到调用我的代码)。如果它在之后做了任何事情，它必须将返回地址设置为0xBBC(加法的地址)。因为它不需要堆栈框架来存储返回地址，所以将递归转换为迭代也更容易。当count调用自身时，它可以直接跳转到该方法的开头。

解决方案（对于这个微不足道的例子）是在另一个参数中累加结果：

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

注意我们什么也不做。

- Matthew Flaschen

---

这确实不太清楚，因为它们都在返回语句中。但是最后一次调用是 1 + result_of_recursion，而不是递归本身。 - extraneon

除了方法返回的位置，它还可以优化掉添加堆栈帧，对吗？ - Mark Peters

@Mark，没错，我会添加一条关于此事的注释。 - Matthew Flaschen

很奇怪，我记得在这里添加了一条评论...无论如何，我的意思是我不知道你在例子中做了什么。为什么要使用地址和程序计数器，让它变得更加复杂呢？无论如何，你可以比较尾递归和前向递归，或者提出一个更清晰（更适合初学者）的解释吗？ - Snowman

@fprime，初学者解释就是在递归调用之后做了一些事情（加法），因此它不能是尾递归。 - Matthew Flaschen

Answer 2

你看过这个stackoverflow问题，尾递归和正向递归的区别吗？

Matthew已经回答了，简要概括一下：

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
}

- extraneon

---

我看到了这个，但是语法很令人困惑。 - Snowman