Matthewacon Matthewacon - 3 months ago 21
Java Question

Achieving Stackless recursion in Java 8

So here is a question that I can't seem to find a good answer to:
How do I achieve stackless recursion in Java?

I have been trying to answer this question for about a month now, and I have not been able to get/find a straight answer (taking into consideration my lack of time because of school). The word that seems to come up the most is "Trampolining", and I have no clue what that means. As such, it would be greatly appreciated if somebody could IN DETAIL explain how to achieve stackless recursion in Java, what "Trampolining" is, and if you cannot do either of those, could somebody please point me in the right direction? (ie. A book to read about it, or some tutorial that teaches all of these concepts)

Answer

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:

Trampoline diagram

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> factorial(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(factorial(n - 1, sum * n));
            }
        };
    }
}

And to call:

Factorial.factorial(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

Comments