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
  }
}