Trampoline

About 2 min

Intent

To optimize recursive function calls by converting them into iterative loops, avoiding stack overflow errors.

Explanation

Real-world example

Imagine you are organizing a relay race. Each runner passes the baton to the next runner until the race is complete. However, if each runner had to physically run back to the starting line to pass the baton to the next runner, the race would be inefficient and error-prone. Instead, runners pass the baton directly to the next runner in line, who continues the race seamlessly.
The Trampoline pattern in programming works similarly by ensuring that each recursive step is handed off efficiently without having to return to the start, preventing a stack overflow (similar to our runners never having to backtrack).

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.

public interface Trampoline<T> {

  T get();

  default Trampoline<T> jump() {
    return this;
  }

  default T result() {
    return get();
  }

  default boolean complete() {
    return true;
  }

  static <T> Trampoline<T> done(final T result) {
    return () -> result;
  }

  static <T> Trampoline<T> more(final Trampoline<Trampoline<T>> trampoline) {
    return new Trampoline<T>() {
      @Override
      public boolean complete() {
        return false;
      }

      @Override
      public Trampoline<T> jump() {
        return trampoline.result();
      }

      @Override
      public T get() {
        return trampoline(this);
      }

      T trampoline(final Trampoline<T> trampoline) {
        return Stream.iterate(trampoline, Trampoline::jump)
            .filter(Trampoline::complete)
            .findFirst()
            .map(Trampoline::result)
            .orElseThrow();
      }
    };
  }
}

Using the Trampoline to get Fibonacci values.

@Slf4j
public class TrampolineApp {

    public static void main(String[] args) {
        LOGGER.info("Start calculating war casualties");
        var result = loop(10, 1).result();
        LOGGER.info("The number of orcs perished in the war: {}", result);

    }

    public static Trampoline<Integer> loop(int times, int prod) {
        if (times == 0) {
            return Trampoline.done(prod);
        } else {
            return Trampoline.more(() -> loop(times - 1, prod * times));
        }
    }
}

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

Applicability

Use the Trampoline pattern when

When dealing with algorithms that use recursion heavily and risk running into stack overflow errors.
When tail-call optimization is not supported by the Java language natively.

Tutorials

Known Uses

Implementing algorithms that require deep recursion, such as certain tree traversals, combinatorial algorithms, and mathematical computations.
Functional programming libraries and frameworks where tail-call optimization is necessary for performance and stack safety.
cyclops-reactopen in new window

Consequences

Benefits:

Prevents stack overflow by converting deep recursion into iteration.
Enhances performance by avoiding the overhead of deep recursive calls.
Simplifies the code by making recursive calls look like a sequence of steps.

Trade-offs:

May introduce additional complexity in terms of understanding and implementing the trampoline mechanism.
Requires converting naturally recursive algorithms into a continuation-passing style.

Iteratoropen in new window: Both patterns aim to transform potentially recursive operations into iterative processes, though the iterator pattern is more general-purpose.
Stateopen in new window: Like the Trampoline, the State pattern can also handle complex state transitions, which can sometimes involve recursive-like state changes.
Strategyopen in new window: This pattern can be related in terms of defining a family of algorithms (or continuations in the case of the Trampoline) and making them interchangeable.