Fibonacci series recursion error

[Terry Reedy]

On 5/1/2011 7:16 PM, BartC wrote:

> Yes, it generates lots of calls.
>
> About 22000 for fib(20), and 330 million for fib(40).

Using the standard double recursion implementation of fib, ncf(n) 
(number of calls to fib() for fib(n)) requires ncf(n-2) + ncf(n+1) + 1 
calls. The +1 is for the call to fib(n) itself). So it grows a bit 
faster than fib(n).

Fib(n) is actually calculated as the sum of fib(n) 1s: 1+1+1....+1 
fib(n) times as 1 is the only non-0 base case and there is nothing else 
added or multiplied in non-base cases. To put it another way, there are 
fib(n) leaf nodes labeled 1 in the unbalanced tree generated by the 
recursion.

-- 
Terry Jan Reedy