Welcome, guest | Sign In | My Account | Store | Cart

New Tail Recursion Decorator (Python recipe) by kay schluehr
ActiveState Code (http://code.activestate.com/recipes/496691/)

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

Python, 63 lines
Download
 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

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.

Tags: algorithms

3 comments

Duncan Booth 17 years, 11 months ago  # | flag

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,), {})
Michele Simionato 17 years, 11 months ago  # | flag

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
George Sakkis 15 years, 7 months ago  # | flag

In Michele's version, CONTINUE should be an instance attribute, not a class attribute, to work for mutually recursive functions (like even/odd). Also __call__ can be simplified a bit:

class tail_recursive(object):

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

    def __call__(self, *args, **kwd):
        if self.firstcall:
            func = self.func
            CONTINUE = self.CONTINUE
            self.firstcall = False
            try:
                while True:
                    result = func(*args, **kwd)
                    if result is CONTINUE: # update arguments
                        args, kwd = self.argskwd
                    else: # last call
                        return result
            finally:
                self.firstcall = True
        else: # return the arguments of the tail call
            self.argskwd = args, kwd
            return self.CONTINUE

As Kay noted, the decorator is beneficial only for large values; on my box (T60, WinXP, Python 2.5), the undecorated factorial is faster for up to N~=1700 (after increasing the default recursion limit).

Created by kay schluehr on Tue, 9 May 2006 (PSF)
◄ Python recipes (4591) ►
◄ kay schluehr's recipes (9) ►

Required Modules

Other Information and Tasks