Achieving Stackless recursion in Java 8

A trampoline is a pattern for turning stack-based recursion into an equivalent loop. Since loops don't add stack frames, this can be thought of as a form of stackless recursion.

Here's a diagram I found helpful:

From bartdesmet.net

You can think of a trampoline as a process that takes a starting value; iterates on that value; and then exits with the final value.

---

Consider this stack-based recursion:

public static int factorial(final int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

For every recursive call this makes, a new frame is pushed. This is because the prior frame cannot evaluate without the result of the new frame. This will become a problem when the stack gets too deep and we run out of memory.

Luckily, we can express this function as a loop:

public static int factorial2(int n) {
    int i = 1; 
    while (n > 1) {
        i = i * n;
        n--;
    }
    return i;
}

What's going on here? We've taken the recursive step and made it the iteration inside of a loop. We loop until we have completed all recursive steps, storing the result or each iteration in a variable.

This is more efficient since fewer frames will be created. Instead of storing a frame for each recursive call (n frames), we store the current value and the number of iterations remaining (2 values).

The generalization of this pattern is a trampoline.

public class Trampoline<T>
{
    public T getValue() {
        throw new RuntimeException("Not implemented");
    }

    public Optional<Trampoline<T>> nextTrampoline() {
        return Optional.empty();
    }

    public final T compute() {
        Trampoline<T> trampoline = this;

        while (trampoline.nextTrampoline().isPresent()) {
            trampoline = trampoline.nextTrampoline().get();
        }

        return trampoline.getValue();
    }
}

The Trampoline requires two members:

• the value of the current step;
• the next function to compute, or nothing if we have reached the last step

Any computation that can be described in this way can be "trampolined".

What does this look like for factorial?

public final class Factorial
{
    public static Trampoline<Integer> createTrampoline(final int n, final int sum)
    {
        if (n == 1) {
            return new Trampoline<Integer>() {
                public Integer getValue() { return sum; }
            };
        }
        
        return new Trampoline<Integer>() {
            public Optional<Trampoline<Integer>> nextTrampoline() {
                return Optional.of(createTrampoline(n - 1, sum * n));
            }
        };
    }
}

And to call:

Factorial.createTrampoline(4, 1).compute()

---

Notes

• Boxing will make this inefficient in Java.
• This code was written on SO; it has not been tested or even compiled

Further reading

• Java Basics: How Call Works
• Stacks and Recursion Elimination
• Wikipedia
• Jumping the Trampoline in C# – Stack-Friendly Recursion
• Reverse Trampoline
• What is a trampoline function?