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
--
http://mail.python.org/mailman/listinfo/python-list
