为什么这是尾递归？

Question

看看这段Scala代码：

def rec(n: Int) {
  if (n > 1) {
    val d = n / 2
    rec(d)
//    if (d > 1)  // abort loop
      rec(n/d)
  }
}

这段代码将会导致无限循环。由于尾递归优化，我不会遇到StackOverflowError。

使用jad反编译后，我得到了以下的Java代码：

public void rec(int n)
{
    int d;
    for(; n > 1; n /= d)
    {
        int i = n;
        d = i / 2;
        rec(d);
    }
}

在循环的最后一行，该方法会调用自身，因此我不理解尾调用位置。有人能解释一下吗？

- kiritsuku

---

这将会很有帮助：1. http://www.cs.wayne.edu/~artem/main/teaching/csc3200ss2006/slides/recursion/types.html 2. https://dev59.com/fXVD5IYBdhLWcg3wDXF3 - Dead Programmer

Answer 1

rec(d)不存在尾调用。对于rec(N)（其中N>1），在log2(N)次调用后，堆栈不再增长（因为此时n将永远等于2或3，而d为1）。之后就是一个带有内部rec(1)调用的无限循环，每次立即返回。这就是为什么没有堆栈溢出的原因。

- hoha

Answer 2

在你的方法的递归形式中，有两个递归调用。 StackOverflowError 是由最后一个调用引起的。

由于尾递归优化，最后一个调用变成了循环（而第一个调用保持递归），因此你会得到无限循环而不是无限递归，并且 StackOverflowError 不会发生。

- axtavt