tail_recursion.py

# Tail recursion in Python

# http://stackoverflow.com/questions/13591970/does-python-optimize-tail-recursion
# As far as the question, does Python inherently support tail recursion?
# No, and it never will since Guido prefers to be able to have proper tracebacks
# http://neopythonic.blogspot.com.au/2009/04/tail-recursion-elimination.html
# http://neopythonic.blogspot.com.au/2009/04/final-words-on-tail-calls.html

# But it's possible to do it with a decorator, and the stack never gets too deep.
# http://code.activestate.com/recipes/496691-new-tail-recursion-decorator/
# I haven't completely wrapped my head around what's going on here. The odd-vs-even
# thing has me a little fogged.

import sys 

EXPLAIN = ('explain' in sys.argv[1:])
if EXPLAIN:
    depth = [0] 
    def enter(x=''):
        print (4 * depth[0] * ' ') + 'enter ' + x 
        depth[0] += 1
    def mumble(x=''):
        print (4 * depth[0] * ' ') + x 
    def exit(x=''):
        depth[0] -= 1
        print (4 * depth[0] * ' ') + 'exit ' + x 

def tail_recursion(g):
    loc_vars = {"in_loop": False, "cnt": 0}

    def result(*args, **kwd):
        if EXPLAIN: enter('g={0}, loc_vars={1}'.format(g, loc_vars))
        loc_vars["cnt"] += 1
        if not loc_vars["in_loop"]:
            loc_vars["in_loop"] = True
            if EXPLAIN: mumble('entering loop')
            while True:
                if EXPLAIN: mumble('calling helper function')
                if EXPLAIN: depth[0] += 1
                tc = g(*args,**kwd)
                if EXPLAIN: depth[0] -= 1
                if EXPLAIN: mumble('helper function returned {0}'.format(tc))
                try:
                    qual, args, kwd = tc
                    if qual == 'continue':
                        continue
                except (TypeError, ValueError):
                    if EXPLAIN: exit('leaving loop')
                    loc_vars["in_loop"] = False
                    return tc
        else:
            if loc_vars["cnt"] % 2 == 0:
                if EXPLAIN: exit('even, continue')
                return ('continue', args, kwd)
            else:
                if EXPLAIN: exit('odd, return single call')
                return g(*args, **kwd)
    return result


def factorial(x):
    # The decorator is applied to the inner helper function.
    @tail_recursion
    def helper(product, x):
        if x <= 1:
            return x * product
        return helper(product * x, x - 1)
    return helper(1, x)

print factorial(3)
print factorial(4)