[Python-Dev] Explicit Tail Calls

[Shane Hathaway]

Shane Hathaway wrote:
> I'm interested in seeing a good way to write tail calls in Python.  Some
> algorithms are more readable when expressed using tail recursion.

About ten seconds after I wrote the previous message, I realized two things:

- It's easy to write "return Return" instead of "raise Return".  So
"raise TailCall" is probably better.

- I can write a complete implementation of this idea with nothing but a
simple decorator.  Check it out!

Shane



class TailCall(Exception):
    def __init__(self, f, *args, **kwargs):
        self.f = f
        self.args = args
        self.kwargs = kwargs


def has_tail_calls(f):
    def tail_call_wrapper(*args, **kwargs):
        try:
            return f(*args, **kwargs)
        except TailCall, e:
            return e.f(*e.args, **e.kwargs)
    tail_call_wrapper.__doc__ = f.__doc__
    return tail_call_wrapper


@has_tail_calls
def fact2(n, v=1):
    """
    >>> fact2(1)
    1
    >>> fact2(2)
    2
    >>> fact2(3)
    6
    >>> fact2(4)
    24
    >>> fact2(20)
    2432902008176640000L
    """
    if not n:
        return v
    else:
        raise TailCall(fact2, n - 1, v * n)


if __name__ == '__main__':
    import doctest
    doctest.testmod()