为什么这个尾递归？

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

在循环的最后一行,该方法调用自身,因此我不理解尾调用位置.谁可以解释这个？

Answer 1

如果没有尾调用rec(d).对于rec(N)(where N > 1)堆栈在log2(N)调用后不再增长(因为之后n永远等于2或3,并且d为1).之后,它只是内部rec(1)调用的无限循环,每次都会立即返回.这就是没有堆栈溢出的原因.