Fibonacci series recursion error

[Steven D'Aprano]

On Mon, 02 May 2011 14:14:20 +0100, Hans Georg Schaathun wrote:

> On Sun, 01 May 2011 18:24:30 -0400, Terry Reedy
>   <tjreedy at udel.edu> wrote:
> :  This does not make linear recursion 'bad', just impractical for
> general :  use on finite-memory machines. While I consider it very
> useful for :  learning, it is unnecessary because it is easy to write an
> iterative :  version. So called tail-recursion optimization saves memory
> by REMOVING :  RECURSION and replacing it with iteration. : (...)
> :  Python does not do this automatically because 1) it can be a semantic
> :  change under some circumstances; 2) one who wants the iterative
> version :  can just as easily write it directly;
> 
> That's the silliest argument I ever heard.

You must be new to the Internet then :)


> The programmer should write
> the code the way he and application domain experts think, i.e. very
> often recursively.  The compiler should generate code the way the CPU
> thinks (most optimally), i.e. iteratively.

Perhaps so, but there can be a huge gulf between what "should" happen and 
what does happen. The CPython implementation is deliberately a naive, not-
very clever compiler. (PyPy seems to be the implementation aiming at 
cutting-edge cleverness.)

Even such simple optimizations as constant folding are very controversial 
among the CPython developers. They have good reasons for their caution: 
optimizing compilers are renowned for breaking code, especially floating 
point code, and there have been cases in Python's history where 
optimizations have broken existing code and needed to be backed out.

The problem is, once you include side-effects, recursion and iteration 
are *not* identical. Specifically, the opposition to tail-recursion 
optimization in Python is that it plays havoc with the tracebacks you get 
in the event of an exception. The argument goes:

* Debugging is harder than writing code in the first place, so it is more 
important to simplify debugging, even at the cost of making some code 
slightly harder to write.

* Recursion doesn't just mean simple recursion where a function calls 
itself, but mutually recursive functions. You could have (say) five 
functions that mutually called each other recursively, and in the event 
of a traceback you need to see the exact calling chain, but that's 
precisely the information that is blown away by tail-recursion 
optimization.

* Tail-recursion is only a special case of recursion, and not a very 
common special case either, so it is hardly worth the extra complexity of 
the compiler to treat it specially.

Regardless of whether you agree with the arguments or not, they're hardly 
"silly".


-- 
Steven