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

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

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

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