TrampolineExample.java

Before -- naive recursion that blows the stack:

static BigInteger factorialNaive(BigInteger n) {
    if (n.compareTo(BigInteger.ZERO) <= 0) return BigInteger.ONE;
    return n.multiply(factorialNaive(n.subtract(BigInteger.ONE)));
}
// factorialNaive(BigInteger.valueOf(10000)) --> StackOverflowError

After -- apply the 3-step recipe:

import org.higherkindedj.hkt.trampoline.Trampoline;
import java.math.BigInteger;

// Step 1: return type is now Trampoline<BigInteger>
static Trampoline<BigInteger> factorial(BigInteger n, BigInteger acc) {
    if (n.compareTo(BigInteger.ZERO) <= 0) {
        return Trampoline.done(acc);             // Step 2: wrap base case
    }
    return Trampoline.defer(() ->                // Step 3: wrap recursive call
        factorial(n.subtract(BigInteger.ONE), n.multiply(acc))
    );
}

// Execute it -- handles 100,000+ iterations without breaking a sweat
BigInteger result = factorial(BigInteger.valueOf(100_000), BigInteger.ONE).run();
System.out.println("Result has " + result.toString().length() + " digits");

Since Trampoline is a monad, you can use map and flatMap to compose results:

// Transform the result after computation
Trampoline<String> described = factorial(BigInteger.valueOf(10_000), BigInteger.ONE)
    .map(r -> "10000! has " + r.toString().length() + " digits");

System.out.println(described.run());

// Sequence two trampolined computations
Trampoline<BigInteger> combined = factorial(BigInteger.valueOf(5), BigInteger.ONE)
    .flatMap(a -> factorial(BigInteger.valueOf(6), BigInteger.ONE)
        .map(b -> a.add(b)));

System.out.println("5! + 6! = " + combined.run()); // 840

Mutual recursion is where Trampoline really shines. Two functions calling each other cannot be unrolled into a simple loop, yet they blow the stack just as fast:

Before:

static boolean isEvenNaive(int n) {
    if (n == 0) return true;
    return isOddNaive(n - 1);
}
static boolean isOddNaive(int n) {
    if (n == 0) return false;
    return isEvenNaive(n - 1);
}
// isEvenNaive(100_000) --> StackOverflowError

After:

import org.higherkindedj.hkt.trampoline.Trampoline;

static Trampoline<Boolean> isEven(int n) {
    if (n == 0) return Trampoline.done(true);
    return Trampoline.defer(() -> isOdd(n - 1));
}

static Trampoline<Boolean> isOdd(int n) {
    if (n == 0) return Trampoline.done(false);
    return Trampoline.defer(() -> isEven(n - 1));
}

// 1,000,000 bounces, constant stack space
System.out.println(isEven(1_000_000).run());  // true
System.out.println(isOdd(999_999).run());     // true

Each call to isEven defers to isOdd and vice versa. The run() loop handles the ping-pong without ever growing the stack.

When traversing large collections with custom applicatives, standard recursive traverse can overflow. TrampolineUtils provides drop-in stack-safe replacements:

import org.higherkindedj.hkt.Kind;
import org.higherkindedj.hkt.trampoline.TrampolineUtils;
import org.higherkindedj.hkt.id.*;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

List<Integer> largeList = IntStream.range(0, 100_000)
    .boxed()
    .collect(Collectors.toList());

Kind<IdKind.Witness, List<String>> result =
    TrampolineUtils.traverseListStackSafe(
        largeList,
        i -> Id.of("item-" + i),
        IdMonad.instance()
    );

List<String> items = IdKindHelper.ID.narrow(result).value();
System.out.println("Traversed " + items.size() + " elements safely");

Key utilities: traverseListStackSafe, map2StackSafe, sequenceStackSafe. Use these when your collection might exceed 10,000 elements.

Trampoline has dedicated JMH benchmarks measuring stack-safe recursion overhead and scaling behaviour. Key expectations:

• Deep recursion (10,000+) completes without StackOverflowError — stack-safe trampolining is working
• Performance scaling is linear with depth — no exponential blowup or quadratic complexity
• factorialTrampoline vs factorialNaive show similar performance at depth 100 — trampoline overhead is minimal for moderate depths
• Non-linear scaling is a warning sign suggesting memory leak or quadratic complexity

./gradlew :hkj-benchmarks:jmh --includes=".*TrampolineBenchmark.*"

See Benchmarks & Performance for full details and how to interpret results.