Fibonacci series recursion error

[Hans Georg Schaathun]

On 02 May 2011 01:09:21 GMT, Steven D'Aprano
  <steve+comp.lang.python at pearwood.info> wrote:
:  Ah, I see where you're coming from now! You think I'm arguing *against* 
:  the use of recursion. Not at all. Earlier in this thread, I said:

Fair enough.  Somebody said something about recursion mainly being
a beginner's error.  I don't think it was you, but I felt that your
argument in context mainly served to reinforce such a view, whether
intended or not.

:  "Consequently, the naive recursive function is ridiculously slow and 
:  memory-hungry.
: 
:  This seems to have give rise to a myth that recursion should be avoided. 
:  What needs to be avoided is *badly thought out* recursion."

Then we agree.

And badly thought-out iteration is as bad as badly thought-out
recursion.

:  To be honest, I don't know what Python does with local variables. But I 
:  *guess* it uses a constant-sized record which points to the locals, 
:  because that's how I'd do it :)

Maybe, but would it be able to treat specially C API functions with 
a large chunk of stack memory used for local variables?

:  Given a choice between a complicated iterative algorithm and a simple 
:  recursive version, there's no prima facie reason to expect the recursive 
:  version to *necessarily* be slower than iteration in Python *merely* 
:  because it uses recursion. As always, if speed is an issue, profile and 
:  identify the bottlenecks before deciding how to fix them.

Then we are on the same page.

And it is becoming increasingly clear how bizarre this discussion is in 
a python context.  The overhead which may be caused by recursion in
hardware is only one of many sources of overhead which one accepts when 
opting to use python in order to gain other benefits.

-- 
:-- Hans Georg