>Friends, it's not entirely clear to me why this is, but I instrumented a copy of fib, and I found that the number of calls in fib(n) was a more or less constan

>Friends, it's not entirely clear to me why this is, but I instrumented a copy of fib, and I found that the number of calls in fib(n) was a more or less constant factor of the result of calling fib. That ratio converges to twice the golden ratio, which means that since fib(n+1) ~= φ * fib(n), then the number of calls in fib(n) is approximately 2 * fib(n+1). I scratched my head for a bit as to why this is and I gave up; the Lord works in mysterious ways. We can model the number of calls with a doubly-recursive function, much like fib itself: calls 0 = 1 calls 1 = 1 calls n = 1 + calls(n-1) + calls(n-2) However, it's easier to work with this if we split into three parts: the base case of fib that adds 0, the base case that adds 1, and the recursive case. If you examine the number of each type of call, you get the following table: add 0: 1, 0, 1, 1, 2, 3, 5 ... = fib(n-1) add 1: 0, 1, 1, 2, 3, 5, 8 ... = fib(n) recurse: 0, 0, 1, 2, 4, 7, 12 ... = fib(n+1)-1 So the total number of calls is fib(n-1) + fib(n) + fib(n+1) - 1. Since fib(n+1) = fib(n) + fib(n-1), we can express the sum as 2 x fib(n+1)-1. And of course, there's an OEIS entry for this sequence: http://oeis.org/A001595 http://oeis.org/A001595. I notice that one of the definitions given there is "odd numbers whose index is a Fibonacci number," which matches our definition nicely, since you can define the set of odd numbers as 2*(n+1)-1.