Tail recursion optimization and recursion in Java

Question

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:

The first doSomething() call would be optimized?
The second doSomething() call would be optimized?
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

The last two lines can be rewritten as doSomething((f < 0) ? (v/2) : (v*2));... — Oliver Charlesworth
– Oliver Charlesworth, Commented Feb 23, 2015 at 9:46
So where is exactly your problem? There are three questions, try to provide an answer. — Kiril
– Kiril, Commented Feb 23, 2015 at 9:46
First of all: optimization is almost never a guarantee. The fact something can be optimized doesn't mean it will, particularly in Java, when code is optimized "just in time". — Giulio Franco
– Giulio Franco, Commented Feb 23, 2015 at 10:01
@GiulioFranco Tail call optimization is a well-defined concept, deterministically (and statically) applied in languages which support it. It is so pervasive, in fact, that a language supporting it can be referred to as a "TCO'd language". — Marko Topolnik
– Marko Topolnik, Commented Feb 23, 2015 at 10:13
@MarkoTopolnik all (or many) optimizations are a well defined concept. What's often not easy to do is to determine if the concept is applicable to the code we write or not. If some language standardizes conditions where tco is applicable and must be applied, that I don't know. — Giulio Franco
– Giulio Franco, Commented Feb 23, 2015 at 10:16

Marko Topolnik · Accepted Answer · 2015-02-23 10:27:28Z

5

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.

edited Feb 23, 2015 at 10:27

answered Feb 23, 2015 at 9:46

Marko Topolnik

201k31 gold badges336 silver badges455 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Francesco Rigoni Over a year ago

I read that Java 8 has some kind of TCO, but I really cannot understand because someone says it has, some other say no.... so final answer is, there's no TCO at all?

Marko Topolnik Over a year ago

There may perhaps be something in HotSpot's JIT compiler (never heard of it personally, though), but there is definitely nothing in the specification of Java. So, since you don't have any guarantee that a certain idiom will not blow the stack, that would be of little use.

ses Over a year ago

what about java 12?

Giulio Franco · Accepted Answer · 2015-02-23 10:13:34Z

0

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).

answered Feb 23, 2015 at 10:13

Giulio Franco

3,25017 silver badges18 bronze badges

2 Comments

Francesco Rigoni Over a year ago

AFAIK TCO can be done if the tail call is the very last instruction, so what happens if I have something like "return doSomething()" as the last instruction? does the return statement count as the last instruction so no TCO can be done?

Marko Topolnik Over a year ago

return doSomething() is the quintessential example of an optimizable tail call. Much more so that just doSomething() because TCO's primary use case are recursive pure functions, which are by definition never void.

Collectives™ on Stack Overflow

Tail recursion optimization and recursion in Java

2 Answers 2

3 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related