Fibonacci series recursion error

[Steven D'Aprano]

On Sun, 01 May 2011 14:15:35 +0100, Hans Georg Schaathun wrote:

> On 01 May 2011 11:56:57 GMT, Steven D'Aprano
>   <steve+comp.lang.python at pearwood.info> wrote:
> :  Just google on "stack overflow crash".
> 
> And I get loads of examples of stack overflows, but I could not see
> anybody linking this to logically correct recursion.  Wikipedia, for
> instance, mentions two common causes, neither of which has anything to
> do with logically correct recursion.

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:

"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."

[Emphasis in original.]




> :  The Python virtual machine knows how big each entry on the stack
> needs to :  be. (I don't, but it's got to be at least the size of a
> pointer.) So :  "number of items" is just a multiplication away from
> "size of the items".
> 
> Does it?  In a conventional stack you need to store all the local
> variables for the function as well.  Thus, there is no limit to how much
> space a single element on the stack may require.

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 :)

I do know that objects in CPython all live in the heap, not on the stack, 
so even if local variables are placed directly on the stack, that's only 
a pointer to the object, not the entire object.


[...]
> But all of this is in principle, and does not constitute any valid
> reason to avoid recursion in practice.  If you want to argue that
> recursion is a bad thing in /practice/ you need a /practical/ argument.

Okay. In *practice*, all else being equal, recursion is less efficient 
than iteration, especially in Python which doesn't optimize tail-
recursion. So if you have a choice between two algorithms which are 
equally simple and clear, and one is recursive and the other uses 
iteration, the one with iteration will be more efficient.

However, and equally in practice, it's unusual to have two equally simple 
algorithms. Usually one or the other will be much simpler than the other, 
and you should avoid "optimizing" code based on hypothetical 
considerations and instead prefer simple code over complicated, unless 
absolutely necessary.

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.



-- 
Steven