Why is this tail recursive?

check out this Scala-code:

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

This code will result in an endless loop. Owing to tail recursive optimization I don't get a StackOverflowError.

Decompiled with jad I got this Jav开发者_JAVA百科a-code:

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

In the last line of the loop the method calls itself therefore I don't understand the tail call position. Anyone who can explain this?

---

There is no tail call in case of rec(d). For rec(N) (where N > 1) stack doesn't grow anymore after log2(N) calls (because after that n is equal to 2 or 3 forever, and d is 1). After that it's just infinite loop with inner rec(1) call which immediately returns each time. That's why there is not stack overflow.

---

In recursive form of your method you have two recursive calls. StackOverflowError is caused by the last of them.

Due to tail recursion optimization, that last call turns into loop (while the first call is kept recursive), therefore you have infinite loop instead of infinite recursion, and StackOverflowError doesn't happen.