In this tutorial we will learn to find Fibonacci series using recursion.
Fibonacci series are the numbers in the following sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ... .
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.
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
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
Fibo(n) Begin if n <= 1 then Return n; else Return Call Fibo(n-1) + Call Fibo(n-2); endif End
/*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; }