Last active
May 3, 2021 14:08
-
-
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.)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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