Trampolining is a technique that decorates recursion as iteration. For a language like Python that does not optimize tail calls, strict tail recursion can be achieved by combining Trampolining with tail calls.

The basic unit of this method is a thunk, which represents an unevaluated operation. The simplest way to create a thunk and simulate an unevaluated operation is to wrap the operation in a parameterless function and save it for later evaluation.

Thunk “unpacks” through invocation.

1
2
>>> my_thunk1 = lambda: sqrt(16384) + 22
>>> my_thunk1()

It can also be nested, which requires multiple unpackages.

1
2
3
4
5
6
>>> my_nested_thunk = lambda: lambda: lambda: 4 * (2 + 3)
>>> thunk2 = my_nested_thunk()
>>> thunk3 = thunk2()
>>> result = thunk3()
>>> result
20

The unpacking of a nested thunk can be accomplished by repeatedly calling it until a value is finally returned. This is the trampolining process.

1
2
3
4
def trampolining(value):
    while callable(value):
        value = value()
    return value

factorial:

1
2
3
4
5
6
7
8
9
10
11
12
def thunk_factorial(n, so_far=1):
    def thunk():
        if n == 0:
            return so_far
        return thunk_factorial(n - 1, so_far * n)
    return thunk

def factorial(n):
    value = thunk_factorial(n)
    while callable(value): # While value is still a thunk
        value = value()
    return value

In each iteration, only one step of the factorial is calculated, and the frame is closed immediately after the calculation is completed. Instead of creating and returning another nested call as return tail_factorial(n - 1, so_far * n) is used in tail_factorial(ordinary tail recursion writing), it returns an unevaluated thunk.