Fibonacci Series

Fibonacci Series

Fibonacci series are the numbers in the following sequence
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …
By definition, the first two numbers are 0 and 1.
And each subsequent numbers in the series is equal to the sum of the previous two numbers.

Fibonacci Recursive Function

F(n) = 1                when n <= 1
     = F(n-1) + F(n-2)  when n > 1
i.e.,
F(0) = 0
F(1) = 1
F(2) = F(2-1) + F(2-2)
     = F(1) + F(0)
     = 1 + 0
     = 2

Find the 6th element of the Fibonacci series i.e., F(5)

Using the formula given above we can write the following.

F0	F1	F2	F3	F4	F5
0	1	1	2	3	5

So, the 6th element i.e., F(5) = 5

Fibonacci Pseudo Code

Fibo(n)
Begin
	if n <= 1 then
	     Return n;
	else
	     Return Call Fibo(n-1) + Call Fibo(n-2);
	endif
End

Fibonacci C Code

/*fibonacci series
recursive and non-recursive
*/

#include <stdio.h>

//function declaration
int fibo(int n);
int nonRecFibo(int n);

int main(){
	//variable declaration
	int n, f;
	
	//input
	printf("Enter n: ");
	scanf("%d", &n);
	
	//recursive
	f = fibo(n);
	printf("Recursive Fibo: %d\n", f);
	
	//non-recursive
	f = nonRecFibo(n);
	printf("Non-Recursive Fibo: %d\n", f);
	
	return 0;
}

//function definition
int fibo(int n){
	if(n <= 1)
		return n;
	else
		return fibo(n-1) + fibo(n-2);
}

int nonRecFibo(int n){
	int i, a, b, f;
	if(n <= 1)
		return n;
	else{
		a = 0, b = 1, f = 0;
		for(i = 2; i <= n; i++){
			f = a + b;
			a = b;
			b = f;
		}
	}
	return f;
}