Achieving Stackless recursion in Java 8

Question

How do I achieve stackless recursion in Java?

The word that seems to come up the most is "trampolining", and I have no clue what that means.

Could someone IN DETAIL explain how to achieve stackless recursion in Java? Also, what is "trampolining"?

If you cannot provide either of those, could you please point me in the right direction (i.e., a book to read about it or some tutorial that teaches all of these concepts)?

Confluence

This question might be a helpful start, as might this answer on Programmers, which touches on trampolines – Leaflet

take a look on this thread about trampoline implementations: https://mcmap.net/q/82951/-what-is-a-trampoline-function – Adopt

Answer 1

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?

Vaporing

above trampoline call gives -1198722684 for factorial.execute(4) – Cherimoya

Answer 2

From Wikipedia:

a trampoline is a loop that iteratively invokes thunk-returning functions

While doing some research on trampolines myself, I stumbled upon the line above. So I did some experimenting on how a thunk will work and or look like in Java. And I got a satisfying result that is worth sharing. It is quite an upgrade from the previous answer since a thunk looks very similar to the recursive function. This is due to the functional interfaces added since java 8.

---

// Recursive
private int factorial(final int number) {
    return (number == 1)
        ? 1 
        : number * factorial(number -1);
}

Compare the recursive way of doing a factorial (above), to the thunk returning version below. Noticed the similarities?

// The thunk returning version
private Pair<Supplier, Long> factorial(long number, long sum){
    return (number == 1)
        ? new Pair<>(null, sum)
        : new Pair<>(() -> factorial(number -1, sum * number), null);
}

I used Java's Pair here, you can consider it as a poor man's Tupel. In your own project you can use polymorphism on the Supplier function, if you prefer that. Either should work.

---

To invoke the thunk returning version, I use the while loop below.

private long trampoline(long number) {
    Pair<Supplier, Long> supplierOrResult = new Pair<>(()-> factorial(number, 1), null);

    while (supplierOrResult.getValue() == null) {
        supplierOrResult = (Pair<Supplier, Long>)supplierOrResult.getKey().get();
    }

    return supplierOrResult.getValue();
}

When you look back at the quote from Wikipedia you see that the while loop here is the trampoline. We have a while loop that invokes a function that returns a thunk!

Amitosis