This is the fourth article in a series on converting recursive algorithms into iterative algorithms. If you haven’t read the earlier articles first, you may want to do so before continuing.
In the first article of our series, we showed that if you can convert an algorithm’s recursive calls into tail calls, you can eliminate those tail calls to create an iterative version of the algorithm using The Simple Method. In this article, we’ll look at another way to eliminate tail calls: the trampoline.
The idea behind the trampoline is this: before making a tail call, manually remove the current execution frame from the stack, eliminating stack build-up.
Execution frames and the stack
To understand why we might want to manually remove an execution frame, let’s think about what happens when we call a function.
The language runtime needs some place to store housekeeping information and any local variables the function may use, so it allocates a new execution frame on the stack.
Then it turns control over to the function.
When the function is done, it executes a return statement.
This statement tells the runtime to remove the execution frame from the stack and to give control (and any result) back to the caller.
But what if the function doesn’t return right away? What if it makes another function call instead? In that case, the runtime must create a new execution frame for that call and push it onto the stack, on top of the current frame. If the function ends up calling itself many times recursively, each call will add another frame to the stack, and pretty soon we will have eaten up a lot of stack space.
Eliminating stack build-up
To avoid this problem, some programming languages guarantee that they will recycle the current execution frame whenever a function makes a tail call. That is, if the function calls some other function (or itself recursively) and just returns that function’s result verbatim, that’s a tail call. In that case, the runtime will recycle the current function’s execution frame before transferring control to the other function, making it so that the other function will return its result directly to the original function’s caller. This process is called tail-call elimination.
But in languages like Python that don’t offer tail-call elimination, every call, even if it’s a tail call, pushes a new frame onto the stack. So if we want to prevent stack build-up, we must somehow eliminate the current frame from the stack ourselves, before making a tail call.
But how?
The only obvious way to eliminate the current frame is to return to our caller.
If we’re to make this work, then, the caller must be willing to help us out.
That’s where the trampoline comes in.
It’s our co-conspirator in the plot to eliminate stack build-up.
The trampoline
Here’s what the trampoline does:
- It calls our function
f, making itself the current caller. - When
fwants to make a recursive tail call to itself, it returns the instructioncall(f)(*args, **kwds). The language runtime dutifully removes the current execution frame from the stack and returns control to the trampoline, passing it the instruction. - The trampoline interprets the instruction and calls
fback, giving it the supplied arguments, and again making itself the caller. - This process repeats until
fwants to return a final resultz; then it returns the new instructionresult(z)instead. As before, the runtime removes the current execution frame from the stack and returns control to the trampoline. - But now when the trampoline interprets the new instruction it will return
zto its caller, ending the trampoline dance.
Now you can see how the trampoline got its name.
When our function uses a return statement to remove its own execution frame from the stack, the trampoline bounces control back to it with new arguments.
Here’s a simple implementation.
First, we will encode our instructions to the trampoline as triples.
We’ll let call(f)(*args, **kwds) be the triple (f, args, kwds),
and result(z) be the triple (None, z, None):
def call(f):
"""Instruct trampoline to call f with the args that follow."""
def g(*args, **kwds):
return f, args, kwds
return g
def result(value):
"""Instruct trampoline to stop iterating and return a value."""
return None, value, NoneNow we’ll create a decorator to wrap a function with a trampoline that will interpret the instructions that the function returns:
import functools
def with_trampoline(f):
"""Wrap a trampoline around a function that expects a trampoline."""
@functools.wraps(f)
def g(*args, **kwds):
h = f
# the trampoline
while h is not None:
h, args, kwds = h(*args, **kwds)
return args
return gNote that the trampoline boils down to three lines:
while h is not None:
h, args, kwds = h(*args, **kwds)
return argsBasically, the trampoline keeps calling whatever function is in h until that function returns a result(z) instruction, at which time the loop exits and z is returned.
The original recursive tail calls have been boiled down to a while loop.
Recursion has become iteration.
Example: factorial
To see how we might use this implementation, let’s return to the factorial example from the first article in our series:
def factorial(n):
if n < 2:
return 1
return n * factorial(n - 1)Step one, as before, is to tail-convert the lone recursive call:
def factorial(n, acc=1):
if n < 2:
return acc
return factorial(n - 1, acc * n)Now we can create an equivalent function that uses trampoline idioms:
def trampoline_factorial(n, acc=1):
if n < 2:
return result(acc)
return call(trampoline_factorial)(n - 1, n * acc)Note how the return statements have been transformed.
Finally, we can wrap this function with a trampoline to get a callable version that we can use just like the original:
factorial = with_trampoline(trampoline_factorial)Let’s take it for a spin:
>>> factorial(5)
120To really see what’s going on, be sure to use the Online Python Tutor’s visualizer to step through the original, tail-recursive, and trampoline versions of the function. Just open this link: Visualize the execution. (ProTip: use a new tab.)
Why use the trampoline?
As I mentioned at the beginning of this article, if you can convert a function’s recursive calls into tail calls – which you must do to use a trampoline – you can also use the Simple Method to convert the function’s recursion into iteration, eliminating the calls altogether.
For example, here’s what the Simple Method does to our original factorial function:
def factorial(n, acc=1):
while n > 1:
(n, acc) = (n - 1, acc * n)
return accThis version is simpler and more efficient than the trampoline version. So why not use the Simple Method always?
The answer is that the Simple Method is tricky to apply to functions that make tail calls from within loops.
Recall that it introduces a loop around a function’s body and replaces recursive tail calls with continue statements.
But if the function already has its own loops, replacing a tail call within one of them with a continue statement will restart that inner loop instead of the whole-body loop, as desired.
In that case, you must add condition flags to make sure the right loop gets restarted, and that gets old fast.
Then, using a trampoline may be a win.
That said, I almost never use trampolines. Getting a function into tail-call form is nine tenths of the battle. If I’ve gone that far already, I’ll usually go the rest of the way to get a tight, iterative version.
Why, then, did we make this effort to understand the trampoline? Two reasons. First, it’s semi-common in programming lore, so it’s best to know about it. Second, it’s a stepping stone to a more-general, more-powerful technique: continuation-passing-style expressions. That’s our subject for next time.
In the meantime, if you want another take on trampolines in Python, Kyle Miller wrote a nice article on the subject: Tail call recursion in Python.
Thanks for reading! As always, if you have questions or comments, please leave a comment on the blog or hit me at @tmoertel.