Browser docs

Trampoline

April 14, 2023 3 min read Behavioral Performance
On this page

Intent

Trampoline pattern is used for implementing algorithms recursively in Java without blowing the stack and to interleave the execution of functions without hard coding them together.

Explanation

Recursion is a frequently adopted technique for solving algorithmic problems in a divide and conquer style. For example, calculating Fibonacci accumulating sum and factorials. In these kinds of problems, recursion is more straightforward than its loop counterpart. Furthermore, recursion may need less code and looks more concise. There is a saying that every recursion problem can be solved using a loop with the cost of writing code that is more difficult to understand.

However, recursion-type solutions have one big caveat. For each recursive call, it typically needs an intermediate value stored and there is a limited amount of stack memory available. Running out of stack memory creates a stack overflow error and halts the program execution.

Trampoline pattern is a trick that allows defining recursive algorithms in Java without blowing the stack.

Real-world example

A recursive Fibonacci calculation without the stack overflow problem using the Trampoline pattern.

In plain words

Trampoline pattern allows recursion without running out of stack memory.

Wikipedia says

In Java, trampoline refers to using reflection to avoid using inner classes, for example in event listeners. The time overhead of a reflection call is traded for the space overhead of an inner class. Trampolines in Java usually involve the creation of a GenericListener to pass events to an outer class.

Programmatic Example

Here’s the Trampoline implementation in Java.

When get is called on the returned Trampoline, internally it will iterate calling jump on the returned Trampoline as long as the concrete instance returned is Trampoline, stopping once the returned instance is done.

 1public interface Trampoline<T> {
 2
 3  T get();
 4
 5  default Trampoline<T> jump() {
 6    return this;
 7  }
 8
 9  default T result() {
10    return get();
11  }
12
13  default boolean complete() {
14    return true;
15  }
16
17  static <T> Trampoline<T> done(final T result) {
18    return () -> result;
19  }
20
21  static <T> Trampoline<T> more(final Trampoline<Trampoline<T>> trampoline) {
22    return new Trampoline<T>() {
23      @Override
24      public boolean complete() {
25        return false;
26      }
27
28      @Override
29      public Trampoline<T> jump() {
30        return trampoline.result();
31      }
32
33      @Override
34      public T get() {
35        return trampoline(this);
36      }
37
38      T trampoline(final Trampoline<T> trampoline) {
39        return Stream.iterate(trampoline, Trampoline::jump)
40            .filter(Trampoline::complete)
41            .findFirst()
42            .map(Trampoline::result)
43            .orElseThrow();
44      }
45    };
46  }
47}

Using the Trampoline to get Fibonacci values.

 1public static void main(String[] args) {
 2    LOGGER.info("Start calculating war casualties");
 3    var result = loop(10, 1).result();
 4    LOGGER.info("The number of orcs perished in the war: {}", result);
 5}
 6
 7public static Trampoline<Integer> loop(int times, int prod) {
 8    if (times == 0) {
 9        return Trampoline.done(prod);
10    } else {
11        return Trampoline.more(() -> loop(times - 1, prod * times));
12    }
13}

Program output:

19:22:24.462 [main] INFO com.iluwatar.trampoline.TrampolineApp - Start calculating war casualties
19:22:24.472 [main] INFO com.iluwatar.trampoline.TrampolineApp - The number of orcs perished in the war: 3628800

Class diagram

alt text

Applicability

Use the Trampoline pattern when

  • For implementing tail-recursive functions. This pattern allows to switch on a stackless operation.
  • For interleaving execution of two or more functions on the same thread.

Known uses

Credits