Recursion

Recursion Causes Stack Overflow

JVMs of Java 8 and higher still don't support tail call optimization. So if you write a recursive method like the following one, you still get StackOverflowError.

public class App {
public static Long termial(final Long n, final Long acc) {
if (n >= 1) {
return termial(n - 1, acc + n);
} else {
return acc;
}
}
public static void main(final String[] args) {
System.out.println(termial(100000L, 0L));
}
}
Exception in thread "main" java.lang.StackOverflowError
at App.termial(App.java:4)
at App.termial(App.java:4)
at App.termial(App.java:4)
at App.termial(App.java:4)
at App.termial(App.java:4)
at App.termial(App.java:4)
at App.termial(App.java:4)
...

No Stack Overflow with Trampoline

It can be solved using TailCalls.trampoline() with small changes in the original method.

Changes required:

  1. In the original method, put the return type in the type parameter of TailCallable.

    e.g.) Long => TailCallable<Long>.

  2. When it's the end case, return the value with TailCalls.done() method.

    e.g.) return acc; => return TailCalls.done(acc);

  3. Use a lambda expression for supplier for the recursive method call.

    e.g.) return termial(n - 1, acc + n); => return () -> termial(n - 1, acc + n);

import j8plus.recursion.TailCallable;
import static j8plus.recursion.TailCalls.*;
public class App {
public static TailCallable<Long> termial(final Long n, final Long acc) {
if (n >= 1) {
return () -> termial(n - 1, acc + n);
} else {
return done(acc);
}
}
public static void main(final String[] args) {
System.out.println(trampoline(termial(100000L, 0L)));
// 5000050000L
}
}