New tail recursion decorator

Alexander Schmolck a.schmolck at gmail.com
Fri May 12 19:15:29 CEST 2006


Duncan Booth <duncan.booth at invalid.invalid> 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



More information about the Python-list mailing list