Fibonacci series recursion error

[BartC]

"Steven D'Aprano" <steve+comp.lang.python at pearwood.info> wrote in message
news:4dbbb7b6$0$29991$c3e8da3$5496439d at news.astraweb.com...
> 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.

Yes, it generates lots of calls.

About 22000 for fib(20), and 330 million for fib(40).

That's why it's popular for benchmarks that measure performance of function
calls. Using an iterative algorithm wouldn't work quite so well...

-- 
Bartc