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