pythonrecursiontail-recursion

Does Python optimize tail recursion?


I have the following piece of code which fails with the following error:

RuntimeError: maximum recursion depth exceeded

I attempted to rewrite this to allow for tail call optimization (TCO). I believe that this code would have been successful if a TCO had taken place.

def trisum(n, csum):
    if n == 0:
        return csum
    else:
        return trisum(n - 1, csum + n)

print(trisum(1000, 0))

Should I conclude that Python does not do any type of TCO, or do I just need to define it differently?


Solution

  • No, and it never will since Guido van Rossum prefers to be able to have proper tracebacks:

    Tail Recursion Elimination (2009-04-22)

    Final Words on Tail Calls (2009-04-27)

    You can manually eliminate the recursion with a transformation like this:

    >>> def trisum(n, csum):
    ...     while True:                     # Change recursion to a while loop
    ...         if n == 0:
    ...             return csum
    ...         n, csum = n - 1, csum + n   # Update parameters instead of tail recursion
    
    >>> trisum(1000,0)
    500500