2

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?

Jim
  • 18,826
  • 34
  • 135
  • 254

3 Answers3

3

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.

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
  • I do not understand the answer. `fib(18)` is called 2 times only. I have all the calls printed. – Jim Sep 16 '17 at 18:08
  • If you call fib(18) directly (e.g. `print fib(18)` or whatever), the result that's returned (not the number of calls) is 2584. – Bernhard Barker Sep 16 '17 at 18:10
  • The complexity of this function is `T(N)=T(N-1) + T(N-2)` which is called as exponential. My question is how do we prove the exponential part so as to be able to calculate that `fib(3)` would be called 2584 times? Saying that `fib(3)` will be called `fib(18)` times does not show me some exponential calculation. This is the part I am confused. – Jim Sep 16 '17 at 18:15
  • Does this answer your question - [Computational complexity of Fibonacci Sequence](https://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence), [Exponential lower bound for Fibonacci numbers](https://math.stackexchange.com/questions/571433/exponential-lower-bound-for-fibonacci-numbers)? – Bernhard Barker Sep 16 '17 at 18:28
  • So I went through the answers. The `fib(n)` is approximated by `e^n`. But the answers are about the steps required to calculated `fib(n)` which is almost `e^n`. They don't say (or I missed the point) for any n e.g. `fib(30)` how do we calculate how many times `fib(3)` is called. Somehow your answer gives a hint that it can be found by `fib(18)` but I didn't really get fully the intuition – Jim Sep 16 '17 at 21:17
1

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!

TNguyen
  • 1,041
  • 9
  • 24
1

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.

גלעד ברקן
  • 23,602
  • 3
  • 25
  • 61