435,011 Members | 2,968 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,011 IT Pros & Developers. It's quick & easy.

New tail recursion decorator

 P: n/a May 10 '06 #1
19 Replies

 P: n/a Kay Schluehr wrote: http://aspn.activestate.com/ASPN/Coo.../Recipe/496691 Neat. Diez May 10 '06 #2

 P: n/a Diez B. Roggisch wrote: Kay Schluehr wrote: http://aspn.activestate.com/ASPN/Coo.../Recipe/496691 Neat. Diez Hi Diez, for all those who already copied and pasted the original solution and played with it I apologize for radical changes in the latest version ( the recipe is on version 1.5 now ! ). The latest implementation is again a lot faster than the previous one. It does not only get rid of exceptions but also of stack-frame inspection. Regards, Kay May 10 '06 #3

 P: n/a Kay Schluehr wrote: Diez B. Roggisch wrote: Kay Schluehr wrote: > http://aspn.activestate.com/ASPN/Coo.../Recipe/496691 Neat. Diez Hi Diez, for all those who already copied and pasted the original solution and played with it I apologize for radical changes in the latest version ( the recipe is on version 1.5 now ! ). The latest implementation is again a lot faster than the previous one. It does not only get rid of exceptions but also of stack-frame inspection. Regards, Kay I'm not convinced by this. You have to recognise that the function is using tail recursion, and then you have to modify the code to know that it is using tail recursion. This is not always trivial. For example, the given example is: @tail_recursion def factorial(n, acc=1): "calculate a factorial" if n == 0: return acc res = factorial(n-1, n*acc) return res but a more common way to write the function would be: @tail_recursion def factorial(n): "calculate a factorial" if n == 0: return 1 return n * factorial(n-1) which won't work because it isn't actually tail recursion, but it looks sufficiently close to tail recursion that it would probably mislead a lot of people into expecting it will work. If you are going to have to rewrite functions in a stilted manner, and they use simple tail recursion, then why not just factor out the tail recursion in the first place. My other problem with this is that the decorator is very fragile although this may be fixable. e.g. (using the published example) an exception thrown inside the function makes future calls return garbage: factorial(3) 6 factorial('a') Traceback (most recent call last): File "", line 1, in -toplevel- factorial('a') File "", line 12, in result tc = g(*args,**kwd) File "", line 6, in factorial res = factorial(n-1, n*acc) TypeError: unsupported operand type(s) for -: 'str' and 'int' factorial(3) ('continue', (3,), {}) May 10 '06 #4

 P: n/a Kay Schluehr wrote: for all those who already copied and pasted the original solution and played with it I apologize for radical changes in the latest version ( the recipe is on version 1.5 now ! ). The latest implementation is again a lot faster than the previous one. It does not only get rid of exceptions but also of stack-frame inspection. This is spectacular!! I would rewrite it as follows: CONTINUE = object() # sentinel value returned by iterfunc def tail_recursive(func): """ tail_recursive decorator based on Kay Schluehr's recipe http://aspn.activestate.com/ASPN/Coo.../Recipe/496691 """ var = dict(in_loop=False, cont=True, argkw='will be set later') # the dictionary is needed since Python closures are read-only def iterfunc(*args, **kwd): var["cont"] = not var["cont"] if not var["in_loop"]: # start looping var["in_loop"] = True while True: res = func(*args,**kwd) if res is CONTINUE: args, kwd = var["argkw"] else: var["in_loop"] = False return res else: if var["cont"]: var["argkw"] = args, kwd return CONTINUE else: return func(*args,**kwd) return iterfunc Using my decorator module 'tail_recursive' can even be turned in a signature-preserving decorator. I think I will add this great example to the documentation of the next version of decorator.py! Michele Simionato May 10 '06 #5

 P: n/a Michele Simionato wrote: Using my decorator module 'tail_recursive' can even be turned in a signature-preserving decorator. I think I will add this great example to the documentation of the next version of decorator.py! Michele Simionato Done: see http://www.phyast.pitt.edu/~micheles.../decorator.zip and http://www.phyast.pitt.edu/~micheles...mentation.html May 10 '06 #6

 P: n/a Em Ter, 2006-05-09 Ã*s 23:30 -0700, Kay Schluehr escreveu: http://aspn.activestate.com/ASPN/Coo.../Recipe/496691 Is it thread safe? -- Felipe. May 11 '06 #7

 P: n/a Michele Simionato wrote: CONTINUE = object() # sentinel value returned by iterfunc def tail_recursive(func): """ tail_recursive decorator based on Kay Schluehr's recipe http://aspn.activestate.com/ASPN/Coo.../Recipe/496691 """ var = dict(in_loop=False, cont=True, argkw='will be set later') # the dictionary is needed since Python closures are read-only def iterfunc(*args, **kwd): var["cont"] = not var["cont"] if not var["in_loop"]: # start looping var["in_loop"] = True while True: res = func(*args,**kwd) if res is CONTINUE: args, kwd = var["argkw"] else: var["in_loop"] = False return res else: if var["cont"]: var["argkw"] = args, kwd return CONTINUE else: return func(*args,**kwd) return iterfunc CONTINUE could be put inside tail_recursive, couldn't it? And to squeeze a little more speed out of it, var could be a list (saves a hash lookup). Cool decorator. Carl Banks May 11 '06 #8

 P: n/a [...] I'm not convinced by this. You have to recognise that the function is using tail recursion, and then you have to modify the code to know that it is using tail recursion. This is not always trivial. For example, the given example is: @tail_recursion def factorial(n, acc=1): "calculate a factorial" if n == 0: return acc res = factorial(n-1, n*acc) return res but a more common way to write the function would be: @tail_recursion def factorial(n): "calculate a factorial" if n == 0: return 1 return n * factorial(n-1) which won't work because it isn't actually tail recursion, but it looks sufficiently close to tail recursion that it would probably mislead a lot of people into expecting it will work. If you are going to have to rewrite functions in a stilted manner, and they use simple tail recursion, then why not just factor out the tail recursion in the first place. [...] Hi Duncan, I don't know why it wouldn't work this way, or why it isn't tail-recursion? I tried the tail_recursion decorator from the cookbook-recipe with both definitions of factorial, and I tried both definitions of the factorial function with and without tail_recursion decorator. In all four cases I get the same results, so it does work with both definitions of factorial(), even if (according to you) the second definition is not proper tail-recursion. Using the tail-recursion decorator (the version that does not inspect the stackframes) I get a small performance-increase over using the factorial-function undecorated. However, calculating factorial(1000) with the factorial-function as defined in the cookbook-recipe is much much faster than calculating the same factorial(1000) with the factorial-function you gave! I cannot yet explain why the first function has so much better performance than the second function - about a factor 10 difference, in both python2.4.3 and python 2.5a2 Cheers, --Tim May 12 '06 #9

 P: n/a Tim N. van der Leeuw wrote: I don't know why it wouldn't work this way, or why it isn't tail-recursion? From the google page do "define: tail recursion" I tried the tail_recursion decorator from the cookbook-recipe with both definitions of factorial, and I tried both definitions of the factorial function with and without tail_recursion decorator. In all four cases I get the same results, so it does work with both definitions of factorial(), even if (according to you) the second definition is not proper tail-recursion. For me factorial(1001) with the second definition does not work, I get the recursion limit (which is what I expect). I suppose the recursion limit is higher on your system, but definitely you should reach it at some point with the non tail-recursive version of factorial. Using the tail-recursion decorator (the version that does not inspect the stackframes) I get a small performance-increase over using the factorial-function undecorated. However, calculating factorial(1000) with the factorial-function as defined in the cookbook-recipe is much much faster than calculating the same factorial(1000) with the factorial-function you gave! I cannot yet explain why the first function has so much better performance than the second function - about a factor 10 difference, in both python2.4.3 and python 2.5a2 It is because the decorator is doing is job (converting a long recursion in a loop) only with the first function, which is properly tail recursive. Just as Duncan said. Michele Simionato May 12 '06 #10

 P: n/a Hi Michele, I'm sorry, but you misunderstood me. There are two definitions of the factorial() function, one given by the OP and the other given by Duncan. I tested both factorial() definitions with, and without the tail_recursion decorator (the version of the OP). So I had 4 factorial-functions defined in my test-file: @tail_recursion def factorial(n, acc=1): # do the stuff pass def factorial_r(n, acc=1): # do the stuff pass @tail_recursion def factorial2(n): # do the stuff pass def factorial2_r(n): # do the stuff pass All four functions give the same output for the tests I did (n=120, and n=1000). Using timeit, both factorial(1000) and factorial2(1000) are somewhat faster than factorial_r(1000) respectively factorial2_r(1000). However, factorial(1000) and factorial_r(1000) are both 10x faster than factorial2(1000) and factorial2_r(1000). It's the latter performance difference which I do not understand. The other thing I do not understand, due to my limited understanding of what is tail-recursion: factorial2 (Duncan's definition) is not proper tail-recursion. Why not? How does it differ from 'real' tail recursion? And if it's not proper tail-recursion and therefore should not work, then how comes that the tests I do show it to work? And I seemed to consistently get a slightly better performance from factorial2(1000) than from factorial2_r(1000). NB: Regarding the recursion limits, I don't know what would be the stacklimit on my system (Python 2.4.3 on WinXP SP2). I already calculated the factorial of 500000 using the recursive (non-decorated) function... Cheers, --Tim May 12 '06 #11

 P: n/a Tim N. van der Leeuw wrote: The other thing I do not understand, due to my limited understanding of what is tail-recursion: factorial2 (Duncan's definition) is not proper tail-recursion. Why not? How does it differ from 'real' tail recursion? Tail recursion is when a function calls itself and then immediately returns the result of that call as its own result. So long as nothing except returning the result needs to be done it is possibly to avoid the recursive call altogether. This function is tail recursive: @tail_recursion def factorial(n, acc=1): "calculate a factorial" if n == 0: return acc res = factorial(n-1, n*acc) return res but this one isn't: @tail_recursion def factorial2(n): "calculate a factorial" if n == 0: return 1 return n * factorial2(n-1) because when the inner call to factorial2() returns the function still has to do some work (the multiplication). I don't understand your comments about speed differences. If you try to run factorial2() as defined above then it simply throws an exception: there are no results to compare. My guess is that when you wrote: @tail_recursion def factorial2(n): # do the stuff pass your 'do the stuff' actually had an erroneous call to 'factorial'. If you are going to rename the function you have to rename the recursive calls as well. (At least, that's what I forgot to do when I first tried it and couldn't understand why it gave me an answer instead of crashing.) The decorator also fails for functions which are tail-recursive but which contain other non-tail recursive calls within themselves. For example I would be pretty sure you couldn't write a working implementation of Ackermann's function using the decorator: def Ack(M, N): if (not M): return( N + 1 ) if (not N): return( Ack(M-1, 1) ) return( Ack(M-1, Ack(M, N-1)) ) May 12 '06 #12

 P: n/a Duncan Booth wrote: Tim N. van der Leeuw wrote: [...] @tail_recursion def factorial2(n): # do the stuff pass your 'do the stuff' actually had an erroneous call to 'factorial'. If you are going to rename the function you have to rename the recursive calls as well. (At least, that's what I forgot to do when I first tried it and couldn't understand why it gave me an answer instead of crashing.) [...] Duncan, You're totally right. Somehow, I had managed to completely overlook this. Oops! My apologies! :) --Tim May 12 '06 #13

 P: n/a Duncan Booth wrote: The decorator also fails for functions which are tail-recursive but which contain other non-tail recursive calls within themselves. For example I would be pretty sure you couldn't write a working implementation of Ackermann's function using the decorator: def Ack(M, N): if (not M): return( N + 1 ) if (not N): return( Ack(M-1, 1) ) return( Ack(M-1, Ack(M, N-1)) ) Definitely. The translation into a proper tail-recursive form is non-trivial but nevertheless possible as demonstrated by the following Ackermann implementation: @tail_recursion def ack(m,n,s=): # use a stack-variable s as "accumulator" if m==0: if s == 1: return ack(s-1,n+1,s) elif s == 0: return n+1 elif n==0: return ack(m-1,1,s) else: return ack(m,n-1,[1,m,s]) Regards, Kay May 12 '06 #14

 P: n/a Duncan Booth writes: Tim N. van der Leeuw wrote: The other thing I do not understand, due to my limited understanding of what is tail-recursion: factorial2 (Duncan's definition) is not proper tail-recursion. Why not? How does it differ from 'real' tail recursion? Tail recursion is when a function calls itself and then immediately returns the result of that call as its own result. I think the definition is broader than that so that these two functions would also be tail-recursive (i.e. the tail call doesn't have to be a self-tail call; I might be mistaken, don't have a good reference at hand; however "properly tail recursive" certainly refers to being able to do the below without exhausting the stack even for large n, not just transforming self-tail calls to a loop, which is sort of limited usefulness anyway): def even(n): return n == 0 or not odd(n-1) def odd(n): return n == 1 or not even(n-1) 'as May 12 '06 #15

 P: n/a Kay Schluehr wrote: Duncan Booth wrote: The decorator also fails for functions which are tail-recursive but which contain other non-tail recursive calls within themselves. For example I would be pretty sure you couldn't write a working implementation of Ackermann's function using the decorator: def Ack(M, N): if (not M): return( N + 1 ) if (not N): return( Ack(M-1, 1) ) return( Ack(M-1, Ack(M, N-1)) ) Definitely. The translation into a proper tail-recursive form is non-trivial but nevertheless possible as demonstrated by the following Ackermann implementation: @tail_recursion def ack(m,n,s=): # use a stack-variable s as "accumulator" if m==0: if s == 1: return ack(s-1,n+1,s) elif s == 0: return n+1 elif n==0: return ack(m-1,1,s) else: return ack(m,n-1,[1,m,s]) Very clever, although simulating a stack isn't exactly eliminating recursion. Any idea how long I have to wait to find ack(4,1)? May 12 '06 #16

 P: n/a "Alexander Schmolck" wrote in message news:yf*************@oc.ex.ac.uk... Duncan Booth writes: Tail recursion is when a function calls itself and then immediately returns the result of that call as its own result. Which means that the value returned by the base case is returned unchanged to the original caller through the stack of returns. Which means that the return stack can potentially be compressed to just one return. I think the definition is broader than that so that these two functions would also be tail-recursive (i.e. the tail call doesn't have to be a self-tail call; I might be mistaken, don't have a good reference at hand; however "properly tail recursive" certainly refers to being able to do the below without exhausting the stack even for large n, not just transforming self-tail calls to a loop, which is sort of limited usefulness anyway): def even(n): return n == 0 or not odd(n-1) def odd(n): return n == 1 or not even(n-1) No, these are not even mutually tail-recursive, assuming that that would make sense. You are calling the not operator function on the results of the recursive calls before returning them. The following *is* tail-recursive: def even(n): assert n >= 0 if n >=2: return even(n-2) return bool(n) The recursive call is effectively a goto back to the top of the function, with n reduced by 2. This looping continues until n < 2. So in Python, we would usually write def even(n): assert n >= 0 while n >= 2: n -=2 return bool(n) Terry Jan Reedy May 12 '06 #17

 P: n/a Your examples are not tail recursive because an extra step is needed before returning from the function call and that step cannot be thrown away! Alexander Schmolck wrote: def even(n): return n == 0 or not odd(n-1)def odd(n): return n == 1 or not even(n-1) -- Regards, Casey May 12 '06 #18

 P: n/a Tail Call Optimization and Recursion are separate concepts! -- Regards, Casey May 13 '06 #19

 P: n/a Duncan Booth wrote: My other problem with this is that the decorator is very fragile although this may be fixable This version should be more robust against exceptions: class tail_recursive(object): """ tail_recursive decorator based on Kay Schluehr's recipe http://aspn.activestate.com/ASPN/Coo.../Recipe/496691 """ 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 May 15 '06 #20

This discussion thread is closed

Replies have been disabled for this discussion. 