Skip to content

Tail Call Optimization

funstruct.util.tailrec

Trampoline-based tail recursion.

Examples:

>>> from funstruct.util.tailrec import tco, tail_call
>>> @tco
... def sum_up_to(n, acc=0):
...     if n == 0:
...         return acc
...     return tail_call(sum_up_to)(n - 1, acc + n)
>>> sum_up_to(100)
5050

tco

Marks a function as tail-call optimized.

Use with tail_call to avoid blowing the call stack on recursive functions.

Source code in funstruct/util/tailrec.py 
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class tco:
    """Marks a function as tail-call optimized.

    Use with tail_call to avoid blowing the call stack on recursive functions.
    """

    def __init__(self, f):
        self.f = f

    def __call__(self, *args, **kwargs):
        ret = self.f(*args, **kwargs)
        while type(ret) is _tail_call:
            ret = ret.handle()
        return ret

tco_async

Marks an async function as tail-call optimized.

Same as @tco but for async functions — awaits each step.

Example::

@tco_async
async def async_sum(n, acc=0):
    if n == 0:
        return acc
    return tail_call(async_sum)(n - 1, acc + n)

await async_sum(10000)  # no stack overflow
Source code in funstruct/util/tailrec.py 
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class tco_async:
    """Marks an async function as tail-call optimized.

    Same as @tco but for async functions — awaits each step.

    Example::

        @tco_async
        async def async_sum(n, acc=0):
            if n == 0:
                return acc
            return tail_call(async_sum)(n - 1, acc + n)

        await async_sum(10000)  # no stack overflow
    """

    def __init__(self, f):
        self.f = f

    async def __call__(self, *args, **kwargs):
        ret = await self.f(*args, **kwargs)
        while type(ret) is _tail_call:
            ret = await ret.handle_async()
        return ret

tail_call(f)

Call a tail-recursive function.

Use in conjunction with @tco.

Example::

@tco
def sum_up_to(n, acc=0):
    if n == 0:
        return acc
    return tail_call(sum_up_to)(n - 1, acc + n)

sum_up_to(10000)  # no stack overflow
Source code in funstruct/util/tailrec.py 
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
def tail_call(f):
    """Call a tail-recursive function.

    Use in conjunction with @tco.

    Example::

        @tco
        def sum_up_to(n, acc=0):
            if n == 0:
                return acc
            return tail_call(sum_up_to)(n - 1, acc + n)

        sum_up_to(10000)  # no stack overflow
    """

    def _f(*args, **kwargs):
        return _tail_call(f, *args, **kwargs)

    return _f