Recursive Tail Calls and Trampolines in Swift
Umberto Raimondi (via Natasha Murashev):
In this post we’ll see how the lack of predictable tail call elimination in Swift could be overcome using trampolines and a few alternatives to recursion will be described.
[…]
A trampoline is not much more than a loop that executes iteratively functions that can either return the next function in the sequence (in form of a thunk or continuation, a data structure that contains the information needed to perform a specific function call) or another kind of value (in this case the content of the accumulator) to signal the end of the iteration.
[…]
And even if this implementation [is] slower than the original one for all the code needed to operate the trampoline that was added, this version solves our biggest issue related to stack exhaustion[…]
