ActiveState Powered by ActiveState

Recipe 496691: New Tail Recursion Decorator

A new tail recursion decorator that eliminates tail calls for recursive functions is introduced.

Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import sys

def tail_recursion_with_stack_inspection(g):
    '''
    Version of tail_recursion decorator using stack-frame inspection.    
    '''
    loc_vars ={"in_loop":False,"cnt":0}
    
    def result(*args, **kwd):
        if not loc_vars["in_loop"]:
            loc_vars["in_loop"] = True
            while 1:            
                tc = g(*args,**kwd)
                try:                    
                    qual, args, kwd = tc
                    if qual == 'continue':
                        continue
                except TypeError:                    
                    loc_vars["in_loop"] = False
                    return tc                                    
        else:
            f = sys._getframe()
            if f.f_back and f.f_back.f_back and \
                  f.f_back.f_back.f_code == f.f_code:
                return ('continue',args, kwd)
            return g(*args,**kwd)
    return result


def tail_recursion(g):
    '''
    Version of tail_recursion decorator using no stack-frame inspection.    
    '''
    loc_vars ={"in_loop":False,"cnt":0}

    def result(*args, **kwd):
        loc_vars["cnt"]+=1
        if not loc_vars["in_loop"]:
            loc_vars["in_loop"] = True
            while 1:            
                tc = g(*args,**kwd)
                try:                    
                    qual, args, kwd = tc
                    if qual == 'continue':
                        continue
                except (TypeError, ValueError):                    
                    loc_vars["in_loop"] = False
                    return tc                                    
        else:
            if loc_vars["cnt"]%2==0:
                return ('continue',args, kwd)
            else:
                return g(*args,**kwd)
    return result


@tail_recursion
def factorial(n, acc=1):
    "calculate a factorial"
    if n == 0:
       return acc
    res = factorial(n-1, n*acc)
    return res

Discussion

It is about 2 months ago that Crutcher Dunnavant published a cute tail recursion decorator that eliminates tail calls for recursive functions in Python i.e. turning recursion into iteration [1]. The new one gets rid of catching exceptions and is faster. The source code shows two versions. The first one uses stack frame inspections just like Crutchers decorator, the second one abandones those and runs twice as fast.

[1] http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474088

Warning: the optimization comes at its price. The dumbed down lookup procedure causes brittleness in certain cases and different @tail_recursion decorators can interfere as in the following counter example:

@tail_recursion def even(n): if n == 0: return True else: return odd(n-1)

@tail_recursion def odd(n): if n == 0: return False else: return even(n-1)

Commenting out one of these decorators let it work again. Crutchers decorator works in both cases and shows the expected bounded sized stack behaviour.

Note also that these decorators are not optimizing and for small argument values they are actually far slower.

Comments

  1. 1. At 1:56 p.m. on 10 may 2006, Duncan Booth said:

    This decorator is a bit fragile. You need to add some error handling to the code. If a call to the decorated function ever raises an exception then all subsequent calls to the function will return garbage. e.g.

    >>> factorial(3)
6
>>> factorial('a')

Traceback (most recent call last):
  File "<pyshell#5>", line 1, in -toplevel-
    factorial('a')
  File "<pyshell#1>", line 12, in result
    tc = g(*args,**kwd)
  File "<pyshell#3>", line 6, in factorial
    res = factorial(n-1, n*acc)
TypeError: unsupported operand type(s) for -: 'str' and 'int'
>>> factorial(3)
('continue', (3,), {})
  2. 2. At 12:48 a.m. on 15 may 2006, Michele Simionato said:

    This version is more robust against exceptions.

    class tail_recursive(object):
    CONTINUE = object() # sentinel

    def __init__(self, func):
        self.func = func
        self.firstcall = True

    def __call__(self, *args, **kwd):
        try:
            if self.firstcall: # start looping
                self.firstcall = False
                while True:
                    result = self.func(*args, **kwd)
                    if result is self.CONTINUE: # update arguments
                        args, kwd = self.argskwd
                    else: # last call
                        break
            else: # return the arguments of the tail call
                self.argskwd = args, kwd
                return self.CONTINUE
        except: # reset and re-raise
            self.firstcall = True
            raise
        else: # reset and exit
            self.firstcall = True
            return result

Sign in to comment