# Fibonacci Series

### Recursion Algorithm

Share

In this tutorial we will learn to find Fibonacci series using recursion.

## 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;
}
``````
Share