How do we calculate number of calls in naive fibonaci?

Question

So the following is not optimized fibonacci function:

sub fib {  
    my ( $n ) = @_;  
    return 1 if( $n == 1 || $n == 2 );  
    return fib( $n - 1 ) + fib( $n - 2 );  
}  

I actually printed the number of times fib(3) was called when we try to find the fibonacci of 20.
It is 2584. fib(2) is called 4181.
As far as I know this algorithm shows exponential behavior.
My question is how could I calculate that fib(3) would have been called 2584 times without actually keeping a counter in the code and printing the function calls? How is the exponential part calculated?

Answer 1

fib(i) gets called directly only from fib(i+1) and fib(i+2), and once for each call.

Thus calls(i) (number of calls of fib(i)) equals calls(i+1) + calls(i+2)

So if we start at m and we try to calculate calls(n), we have the following:

calls(m)   = 1             (= fib(1))
calls(m-1) = 1             (= fib(2))
calls(m-2) = 2 (1+1)       (= fib(3))
calls(m-3) = 3 (1+2)       (= fib(4))
calls(m-4) = 5 (2+3)       (= fib(5))
...

This is just the Fibonacci sequence where we want to calculate the m-n+1-th number
(to see why it's exactly m-n+1, consider when n = m, which should be fib(1)).

calls(n) = fib(m-n+1)

We can use an optimised Fibonacci function here to efficiently (in linear time) calculate fib(m-n+1), which will be the number of calls of fib(n) there will be in the unoptimised version.

---

For your example, fib(3) gets called 2584 times if you call fib(20).
fib(20-3+1) = fib(18) = 2584.

---

Note: calls(1) = calls(3) (since fib(2) doesn't call fib(1)), so that's a special case.

Answer 2

I believe it is the Fibbonaci number at Target - desired number + 1 so in the case of asking what is the number of times fib(3) is called in fib(20) it would be the value of fib(20 - 3 + 1) (which is fib(18) = 2584).

If you draw out a tree representing the fibbonaci calls you can see this for yourself!

Answer 3

Dukeling is showing you the sequence that leads to how many times fib(3) is called: fib(20) (m) gets called once, fib(19) (m-1) once, then fib(18) gets called each time fib(19) or fib(20) are called which totals 1+1.

As we move down the sequence on the way to finding how many times fib(3) is called, you'll notice that the numbers (and calculation) correspond with the Fibonacci sequence itself. We go from 20 down to 3 so m - n + 1 steps, and each step corresponds with the next Fibonacci number. By the time we reach how many times fib(3) (fib(n)) is called, the sequence has come to the m-n+1th Fibonacci number, which corresponds with how many times f(n) is called during the unoptimised recursion.