On Wednesday, October 2, 2013 3:00:41 AM UTC+5:30, Terry Reedy wrote: > Part of the reason that Python does not do tail call optimization is > that turning tail recursion into while iteration is almost trivial, once > you know the secret of the two easy steps. Here it is.
What happens for mutual tail recursive code like this def isodd(x) : return False if x==0 else iseven(x-1) def iseven(x): return True if x==0 else isodd(x-1) ---------------- Notes: 1. I am not advocating writing odd/even like the above -- just giving a trivial example 2. General mutual structural (what you call 'body') recursion is more general than mutual tail recursion is more general than single tail recursion. 3. IOW tail recursion optimization is intermediate between the optimization you are showing and the maximally pessimistic implementation -- stack, activation record etc -- of programming languages 4. There is a whole spectrum of such optimizaitons -- 4a eg a single-call structural recursion example, does not need to push return address on the stack. It only needs to store the recursion depth: If zero jump to outside return add; if > 0 jump to internal return address 4b An example like quicksort in which one call is a tail call can be optimized with your optimization and the other, inner one with 4a above 5. Programming language implementations dont do optimizations like TR because these analyses are in themselves hard but because inter-procedural analysis per se is a headache. For python-like languages its a much bigger headache because the recursive name must be dynamically fetched for every call 6. [Personal pov] TR optimization is not really a big beef for me: As you can see, it does not figure in the "All things every programmer should learn from FP" list of mine http://blog.languager.org/2012/10/functional-programming-lost-booty.html 7. Pedagogically, understanding general recursion is far more important than exploiting tail recursion -- https://mail.python.org/mailman/listinfo/python-list
