Skip to content

Instantly share code, notes, and snippets.

@marksto
Last active May 3, 2021 14:08
Show Gist options
  • Save marksto/cce51e44e2716f97812f7f73eec3f409 to your computer and use it in GitHub Desktop.
Save marksto/cce51e44e2716f97812f7f73eec3f409 to your computer and use it in GitHub Desktop.
Tail call recursion for Java 8. And although you may call it trampolining, it does the job of a factorial calculation in Java 8. (One may also implement this in good ol' Java 6 with anonymous local classes. This should be less memory-efficient and this won't leverage the 'java.lang.invoke' package at all. Nonetheless, it will do the job.)
package marksto.lang;
import java.math.BigInteger;
import java.util.stream.Stream;
public class TailCallJava8 {
@FunctionalInterface
public interface TailCall<T> {
TailCall<T> apply();
default boolean isComplete() {
return false;
}
default T result() {
throw new IllegalStateException("Not implemented");
}
default T get() {
return Stream.iterate(this, TailCall::apply)
.filter(TailCall::isComplete)
.findFirst().get()
.result();
}
static <T> TailCall<T> done(final T value) {
return new TailCall<T>() {
@Override
public boolean isComplete() {
return true;
}
@Override
public T result() {
return value;
}
@Override
public TailCall<T> apply() {
throw new IllegalStateException("Not implemented");
}
};
}
}
public static BigInteger factorial(long n) {
return factorial(BigInteger.ONE, n).get();
}
private static TailCall<BigInteger> factorial(BigInteger product, long n) {
if (n == 1) {
//Thread.dumpStack(); // check that there's only 1 call to 'factorial'
return TailCall.done(product);
}
return () -> factorial(BigInteger.valueOf(n).multiply(product), n - 1); // 'invokedynamic' magic happens here
}
public static void main(String[] args) {
System.out.println(factorial(30_000));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment