Fibonacci Series

Fibonacci series => 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

I`th number in series is sum of (i-1)th & (i-2)th number in series where first two number in series are 0 & 1 ,these are base case for Fibonacci series.

If Fibonacci(n) represent n`th number in Fibonacci series .
then
 Fibonacci(0) = 0
 Fibonacci(1) = 1
 .
 .
 .
Fibonacci(n) = Fibonacci(n-1)+Fibonacci(n-2)

Using Iteration you can easily find nth Fibonacci number .

Recursive Method for Finding n`th fibonacci Number .

1. //C Program
2. // Recursive way of finding nth fibonacci number
3. // http://beginer2cs.blogspot.com
5. #include<stdio.h>
7. int fibo_recursion(int n)
8. {
9.    //base case
10.    if(n==0)
11.       return 0;
12.    else if(n==1) //base case
13.            return 1;
14.         else
15.            return (fibo_recursion(n-1)+fibo_recursion(n-2));
16. }
18. main(){
19. int n;
20. printf("Enter n: ");
21. scanf("%d",&n);
22. printf(" %d th Fibonacci number is = %d \n",n,fibo_recursion(n));
24. }

\
This Approach is also called top down approach . this is very inefficient way of calculating n`th Fibonacci number as many calculation is repeated  we can see in this graph

Dynamic Programming Approach reduce calculation Very efficiently . In this approach we store result of each calculation for further use in future & We fallow bottom-top approach instead of top-bottom approach (previous approach).
In bottom-top approach  we first calulate 1st then 2nd ....... then n`th  element .

Now Lets Solve a ProjectEuler question based on This Approach

1. Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
3.                                        1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
5. By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

1. //C Program
2. //We gonna Use bottom up approch i.e Dynamic Programming aprroch
3. //http://beginer2cs.blogspot.com
4. //ProjectEuler Q2
5. #include<stdio.h>
6. main(){
8.   long int Even_sum=0;
9.   int arr[10000];
10.   int i;
12.   //base case
13.   arr[0]=1; //requirement of this particuler Question
14.   arr[1]=1;
16.   for(i=2;i<10000;i++){
17.        arr[i]=arr[i-1]+arr[i-2]; //store result in array
18.        if(arr[i]>=4000000)       //i`th index of array represent i`th Fibonacci number
19.              break;
20.        else
21.           if(arr[i]%2==0)
22.              Even_sum =Even_sum+arr[i];
23.    }
24. printf("Sum of Even Fibbo Number bellow 4 million is = %ld\n",Even_sum);
25. }

Output is : Sum of Even Fibbo Number bellow 4 million is = 4613732
            HoW number of calculation reduces in this approch

Thanks You