I am reading an analysis of a fibanocci number program, shown below. It is mentioned that this implementation is inefficient. Indeed, the number of recursive calls to compute Fn is F(n+1).
My question is: what does "the number of recursive calls to compute Fn is F(n+1)" mean?
int F(int i)
{
if (i < 1) return 0;
if (i == 1) return 1;
return F(i-1) + F(i-2);
}
The naive implementation to compute fibonacci numbers takes F(n+1) recursive calls to compute the number F(n); i.e. to compute f(10)=55 you need 89 recursive calls, and 89 is F(11).
If we want to compute Nth Fibonacci number F(n)=F(n-1)+F(n-2) .We can do it with iteration method and recursive method. if we do it with iterative method
#include<stdio.h>
main()
{
int a=0,b=1,c,i,n;
//clrscr();
printf("enter the limit of series\n");
scanf("%d",&n);
if(n==0)
printf("%d\n",a);
else
printf("%d\n%d\n",a,b);
for(i=2;i<=n;i++)
{
c=a+b;
printf("%d\n",c);
a=b;
b=c;
}
}
It takes O(n) time as it iterates from i=0 to N.
But with recursive method
int F(int i)
{
if (i < 1) return 0;
if (i == 1) return 1;
return F(i-1) + F(i-2);
}
The recurrence relation is
___________ 0 if(n<=0)
/___________ 1 if(n==1)
Fibonacci(n) ____/
\
\___________ Fibonacci(n-1)+Fibonacci(n-2)
So our problem for n = sub-problem of (n-1) + sub-problem of (n-2) hence our time function T(n) is as follows
T(n)=T(n-1)+T(n-2)+O(1)
T(n)={T(N-2)+T(n-3)}+T(n-2) since T(n-1)=T(n-2)+T(n-3) -------- equation(1)
from above you can see T(n-2) is calculated twice. If we expand the recursion tree for N=5 . The recursion tree is as follows
Fib(5)
|
_____________________/ \__________________
| |
Fib(4) + fib(3)
| |
_______/ \_______ ________/ \_______
| + | | + |
Fib(3) Fib(2) Fib(2) Fib(1)
| | |
_______/ \____ ____/ \_______ _______/ \_____
| + | | + | | + |
Fib(2) Fib(1) Fib(1) Fib(0) Fib(1) Fib(0)
_______/ \_______
| + |
Fib(1) Fib(0)
If we observe the recurrsion tree we find that Fib(1) is caliculated 5 times Fib(2) is caliculated 3 times Fib(3) is caliculated 2 times
So using recursion we are actually doing redundant computations . If you use iterative method these redudant calculations are avoided.
T(n)=T(n-1)+T(n-2)+1
From previous SO post Computational complexity of Fibonacci Sequence
complexity of program is approximately equal to bigoh(2power(n)) . Since O(n) < O(2powerN) recursive method is not efficient.
"complexity of program is approximately equal to bigoh(2power(n)) . Since O(n) < O(2powerN) recursive method is not efficient. "
If they compute this complexity in terms of the amount of recursive calls needed, then I don't know where they get 2^n. The graph doesn't model 2^n at all, for larger values the modeling decays significantly. By the 30th term of 832,040, it takes 2,692,536 recursive calls to compute it, far less than 2^30 which is over 1 billion. It's less than 1%!
It means that to calculate the Fibonacci number of 10 numbers you need to run the recursion 10+1 times to obtain it. There are various algorithm that could improve this timeline.
Look at this post here which explains the time complexity of finding Fibonacci numbers and their improvement: Computational complexity of Fibonacci Sequence
Here is my algo for fibonacci
#include<stdio.h>
main()
{
// If we walk backwards in the fibonacci series, the values before
// zero will be 1 and -1. i.e the series can be re imagined as
// -1, 1, 0, 1, 1, 2, 3.
// This will spare us from adding special handling for first
// and second element of the series
int a=-1,b=1,c,i,n;
printf("enter the limit of series\n");
scanf("%d",&n);
printf("The series is : ");
for(i=1;i<=n;i++)
{
c=a+b;
printf("%d\n",c);
// move a and b forward
a=b;
b=c;
}
}
This is some improved version of fibonacci where we compute fibonacci of number only once:
dicFib = { 0:0 ,1 :1 }
iterations = 0
def fibonacci(a):
if (a in dicFib):
return dicFib[a]
else :
global iterations
fib = fibonacci(a-2)+fibonacci(a-1)
dicFib[a] = fib
iterations += 1
return fib
print ("fibonacci of 10 is:" , fibonacci(10))
print ("fibonacci of all numbers:" ,dicFib)
print ("iterations:" ,iterations)
# ('fibonacci of 10 is:', 55)
# ('fibonacci of all numbers:', {0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55})
# ('iterations:', 9)
Here we are storing fibonnaci of each number in dictionary. So you can see it calculates only once for each iteration and for fibonacci(10) it is only 9 times.
