Fibonacci series recursion error

[Steven D'Aprano]

On Sat, 30 Apr 2011 08:32:55 +0200, Peter Otten wrote:

> harrismh777 wrote:
> 
>> Ian Kelly wrote:
>>> since the fact is that if
>>> the function were properly coded, the call stack for fib(20) would
>>> never be more than 20 entries deep at any one time.
>>>
>>>
>> Not so much... and much more !....
>> 
>> 
>> ...  because each recursion level 'return' calls fib() twice, and each
>> of those calls fib() twice, and you get the point...
> 
> I don't understand what you are trying to say -- but it's wrong ;)


I don't know what M Harris thinks he is trying to say either, but the 
*naive* Fibonacci recursive algorithm is particularly badly performing 
and should be avoided. It's ironic that of the two classic algorithms 
used for teaching beginner programmers about recursion, neither is useful 
in practice.

Except for fib(0) and fib(1), each call to fib() results in multiple 
recursive calls. E.g. calling fib(4) results in the following sequence of 
calls:

    fib(4)                                # first call
    => fib(3) + fib(2)                    # three calls
    => fib(2) + fib(1) + fib(1) + fib(0)  # seven calls
    => fib(1) + fib(0) + 1 + 1 + 0        # nine calls
    => 1 + 0 + 1 + 1 + 0 = 3

Thus requiring nine function calls to calculate fib(4) and a maximum 
stack depth of four. As n increases, the number of calls increases at a 
rate significantly faster than the Fibonacci sequence itself, making it 
much worse than O(N**2) but not quite as bad as O(2**N):

    n      = 0   1   2   3   4   5   6   ... 35       ...
    fib(n) = 0   1   1   2   3   5   8   ... 9227465  ...
    calls  = 1   1   3   5   9   15  25  ... 29860703 ...

The number of calls is given by a recursive function with a similar form 
as that of Fibonacci. As far as I know, it doesn't have a standard name, 
but I'll call it R(n):

R(n) = R(n-1) + R(n-2) + 1, where R(0) = R(1) = 1

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. More sensible 
recursive forms performs much better. I leave them as an exercise for 
those who care, or an exercise in googling for those who care a little 
less *wink*



-- 
Steven