Stack-Safety And Recursion

Its common to use recursion rather than looping in pure functional programming to avoid mutating a local variable.

Consider e.g the following implementation of the factorial function:

def factorial(n: int) -> int:
    if n == 1:
        return 1
    return n * factorial(n - 1)

Called with a large enough value for n, the recursive calls will overflow the python stack.

A common solution to this problem in other languages that perform tail-call-optimization is to rewrite the function to put the recursive call in tail-call position.

def factorial(n: int) -> int:

    def factorial_acc(n: int, acc: int) -> int:
        if n == 1:
            return acc
        return factorial_acc(n - 1, n * acc)

    return factorial_acc(n, 1)

In Python however, this is not enough to solve the problem because Python does not perform tail-call-optimization.

Because Python doesn't optimize tail calls, we need to use a data structure called a trampoline to wrap the recursive calls into objects that can be interpreted in constant stack space, by letting the function return immediately at each recursive step.

from pfun.trampoline import Trampoline, Done, Call


def factorial(n: int) -> int:

    def factorial_acc(n: int, acc: int) -> Trampoline[int]:
        if n == 1:
            return Done(acc)
        return Call(lambda: factorial_acc(n - 1, n * acc))

    return factorial_acc(n, 1).run()

However note that in most cases a recursive function can be rewritten into an iterative one that looks completely pure to the caller because it only mutates local variables:

def factorial(n: int) -> int:
    acc = 1
    for i in range(1, n + 1):
        acc *= i
    return acc

This is the recommended way of solving recursive problems (when it doesn't break referential transparency), because it avoids overflowing the stack, and is often easier to understand.