CODEWITHSUNDEEP
javarecursiontail-call-optimizationtail-call
Francesco Rigoni
Francesco Rigoni

Reputation: 983

Tail recursion optimization and recursion in Java

I have a question about tail calls optimization, I need to know how this java code behaves:

private void doSomething(int v) {

    inf f = someCalculation(v);

    if (f < 0) doSomething(v/2);
    else doSomething(v*2);

}

This code is a nonsense example but my question is, in such a case:

  1. The first doSomething() call would be optimized?
  2. The second doSomething() call would be optimized?
  3. The if/else block affects in any way the optimization?

Thanks

EDIT:

Please provide an example on how you would do this if the language was not Java but something else that has TCO

Upvotes: 1

Views: 2348

Answers (2)

Marko Topolnik
Marko Topolnik

Reputation: 200266

Java 8 has no Tail Call Optimization whatsoever. No calls will be optimized (turned into iteration/goto statements).

The discussion over TCO for Java has a long history, though, with Guy Steele being one of its best-known proponents.

I recommend reading this post from the mlvm-dev mailing list for a recent review of the subject.

Upvotes: 5

Giulio Franco
Giulio Franco

Reputation: 3230

Try running the following code:

public static void main(String[] args) {
  for (int i = 1; i > 0; i *= 2) { doSomething(i); }
}

private static void doSomething(int start) {
  doSomething(start, start);
}

private static void doSomething(int i, int start) {
  if (i == 0) { System.out.println("done from " + start); }
  else { doSomething(i - 1, start); }
}

If the JVM can run it without stack overflow, then it should mean it can do tail recursion optimization (or a very good constant propagation).

Upvotes: 0

Related Questions