Lucid Glitch

Tail Call Recursion in Java

Java lacks support for tail call optimization. This means you can’t rely on deep recursion when traversing tree structures or modeling state machines. A simple recursive function that runs fine in many functional languages will blow the stack in Java — even when the call is in tail position.

Fortunately, you can use the trampoline technique to achieve stack-free recursion. It’s not difficult, and it opens the door to a cleaner, more functional style of programming — even in Java. Your code becomes simpler, and the need for mutable variables often disappears.

A simple example

The following code throws StackOverflowException, as it tries to call itself 200,000 times before returning "Foo":

static String foo(int a) {
  // This will eventually cause a StackOverflowError
  return a > 200000 ? "Foo" : foo(a + 1);
}

foo(0);

Instead of executing the recursive call directly, we wrap it in a lambda, a Supplier, and let the trampoline evaluate it in a loop — avoiding stack growth entirely.

static Supplier<Continuation<String>> foo(int a) {
  return () -> a > 200000 ? done("Foo") : recur(foo(a + 1));
}

trampoline(foo(0));

The difference is the return value, a Supplier of a Continuation, returned as a lambda, and that those Continuations are created with calls to done and recur. Most importantly, this version won’t fail like the first one.

The trampoline repeatedly evaluates the Supplier, which yields a Continuation. If it is produced by done, we have reached a final result. If it comes from recur, we continue by calling the next step, seemingly recursivly.

The Continuation looks like:

public class Continuation<V> {
    public final Supplier<Continuation<V>> fun;
    public final V value;

    private Continuation(Supplier<Continuation< V>> fun, V value) {
       this.fun = fun;
       this.value = value;
    }
}

The Continuation holds either a final value or a reference to the next function to call. The trampoline will simply continue as long as a recur step is available, and eventually return the result with done:

import java.util.function.Supplier;

public class Trampoline {

    public static < V> Continuation<V> recur(Supplier<Continuation<V>> f) {
        return new Continuation<>(f, null);
    }

    public static <V> Continuation<V> done(V v) {
        return new Continuation<>(null, v);
    }

    public static <V> V trampoline(Supplier<Continuation<V>> fun) {
        Continuation< V> ret = Continuation.nil();
        while (fun != null) {
            ret = fun.get();
            fun = ret.fun;
        }
        return ret.value;
    }
}

import java.util.function.Supplier;

public class Trampoline {

    public static class Continuation<V> {
        public final Supplier<Continuation<V>> fun;
        public final V value;

        private Continuation(Supplier<Continuation< V>> fun, V value) {
            this.fun = fun;
            this.value = value;
        }

        private static <V> Continuation<V> nil() {
            return new Continuation<>(null, null);
        }
    }

    public static < V> Continuation<V> recur(Supplier<Continuation<V>> f) {
        return new Continuation<>(f, null);
    }

    public static <V> Continuation<V> done(V v) {
        return new Continuation<>(null, v);
    }

    public static <V> V trampoline(Supplier<Continuation<V>> fun) {
        Continuation< V> ret = Continuation.nil();
        while (fun != null) {
            ret = fun.get();
            fun = ret.fun;
        }
        return ret.value;
    }
}

Examples

A classic example is the factorial function:

    long factorial(int n){
        return trampoline(factorial(0, n));
    }
    Supplier<Continuation<Long>> factorial(long acc, int n) {
        return () -> n == 0 ? done(acc) : recur(factorial(acc * n, n - 1));
    }

Even mutual recursion — notoriously tricky in Java — works beautifully. Here’s a version of the classic even/odd check, where two functions even or odd call each other with descreas value until the hit 0:

static Supplier<Continuation<Boolean>> isEven(int a) {
  return () -> a == 0 ? done(true) : recur(isOdd(a - 1));
}

static Supplier<Continuation<Boolean>> isOdd(int a) {
  return () -> a == 0 ? done(false) : recur(isEven(a - 1));
}

trampoline(isEven(200000));

Why Use Recursive Loops?

So what’s the benefit of recursive looping instead of traditional ones?

They reduce complexity by minimizing side effects. With trampolines, recursion becomes stack-safe and often clearer in expressing intent, especially in computations that naturally unfold recursively, like tree traversal or state machines.

You end up with less variables and simpler code.