Why is this tail recursive?

Question

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 Java-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?

This will be be helpful 1.http://www.cs.wayne.edu/~artem/main/teaching/csc3200ss2006/slides/recursion/types.html 2.http://stackoverflow.com/questions/105834/does-the-jvm-prevent-tail-call-optimizations — Dead Programmer, Mar 17 '11 at 09:43

score 9 · Accepted Answer · answered Mar 17 '11 at 10:06

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.

score 3 · Answer 2 · answered Mar 17 '11 at 09:37

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.

Why is this tail recursive?

2 Answers2