Iterative vs. Recursive coding

Hrvoje Niksic hniksic at
Sun Aug 22 19:32:51 CEST 2010

Steven D'Aprano <steve at> writes:

> * It throws away information from tracebacks if the recursive function 
> fails; and
> If you're like me, you're probably thinking that the traceback from an 
> exception in a recursive function isn't terribly useful.

Agreed.  On the other hand, a full-fledged tail recursion optimization
might throw away more than that.  For tail recursion elimination to work
for those used to it, it needs to also handle the case of mutually
recursive tail calls.  The obvious way is by eliminating *all* tail
calls, not just recursive ones.

Tail call optimization, as opposed to tail recursion optimization, means
that code such as:

def f(n):
  return g(n + 5)

is executed by a conceptual "jump" from the body of f to the body of g,
regardless of whether recursion is involved at any point in the call
chain.  Now, if invocation of g() fails, the stack trace will show no
sign of f() having been invoked.  On the other hand, if f() invocation
remains stored on the stack, mutually recursive functions will overflow
it.  Python being dynamic, I would expect it to be impossible to
determine at compile-time whether a tail call will ultimately lead to a
recursive invocation.

More information about the Python-list mailing list