Functional and Concurrent Programming: Core Concepts and Features

Chapter 14

Case Study: Trampolines

The Scala compiler optimizes (most) tail recursive functions and generates code that implements them as loops. Other languages, like Java, do no such thing. Even in Scala, tail-calls outside tail recursive functions are not optimized. This case study implements trampolines, a classic strategy used for tail-call optimization. It shows how trampolines can be used to implement tail recursive calls without growing the execution stack, even in Java. The strategy is then refined to handle non-tail-calls.

14.1 Tail-Call Optimization

Recall our earlier discussion of tail recursive functions in Section 6.5. Some compilers, including Scala’s, optimize the implementation of functions that make a single recursive call ...