Fibonacci numbers are the numbers that form the series called Fibonacci series and are represented as Fn. The first two Fibonacci numbers are 0 and 1 respectively i.e. F0=0 and F1=1. Starting from the third Fibonacci number each Fibonacci number is the sum of its previous two numbers in the series.
Fn = Fn-1 + Fn-2
Table of Contents
The fibonacci series – 0, 1, 1, 2, 3, 5, 8, 13……
Given an integer n. Find the nth Fibonacci number.
Example
Input: n=5
Output: 5
Input: n=9
Output: 34
Recursive Method
Algorithm
- Initialise a variable n.
- Base case – if n is less than equal to 1 return n.
- Recursive case – return fn (n-1) + fn (n-2).
Time Complexity : O(1.6180)n (1.6180 is also known as the golden ratio)
Space Complexity : O(1)
C++ Program for Fibonacci numbers
#include<bits/stdc++.h>
using namespace std;
int fn(int n){
if(n<=1)
return n;
return fn(n-1) + fn(n-2);
}
int main (){
int n=6;
cout<<fn(n);
return 0;
}Output : 8
Java Program for Fibonacci numbers
class fibNumbers{
static int fn(int n){
if(n<=1)
return n;
return fn(n-1) + fn(n-2);
}
public static void main (String args[]){
int n = 6;
System.out.println(fn(n));
}
}Output : 8
Recursive tree for the above code
We can see from the above tree that some functions are being called more than once.
Dynamic Programming Method
Re-calculations of same functions like above can be avoided using DP.
Algorithm
- Initialize a variable n and an array f to store Fibonacci numbers.
- Initialize the first two elements of array as 0 and 1 respectively..
- Traverse all the values till n starting from 2 one by one and update the array values as the sum of the previous two elements in array.
- Return f[n].
Time Complexity: O(n)
Space Complexity: O(n)
C++ Program for Fibonacci numbers
#include<bits/stdc++.h>
using namespace std;
int fn(int n){
int f[n+2];
f[0] = 0;
f[1] = 1;
for(int i=2; i<=n; i++){
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
int main (){
int n = 6;
cout<<fn(n);
return 0;
}Output : 8
Java Program for Fibonacci numbers
class fibNumbers{
static int fn(int n){
int[] f = new int[n+2];
f[0] = 0;
f[1] = 1;
for(int i=2; i<=n; i++){
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
public static void main (String args[]){
int n = 6;
System.out.println(fn(n));
}
}Output : 8
More space-optimized Method
Algorithm
- Initialise three variable x=0, y=1, z.
- Traverse all the values till n starting from 2 one by one and update z as the sum of x and y, x=y, and y=z.
- Return y.
Time Complexity: O(n)
Space Complexity: O(1)
C++ Program for Fibonacci numbers
#include<bits/stdc++.h>
using namespace std;
int fn(int n){
int x=0, y=1, z;
for(int i=2; i<=n; i++){
z = x + y;
x = y;
y = z;
}
return y;
}
int main (){
int n = 6;
cout<<fn(n);
return 0;
}Output : 8
Java Program for Fibonacci numbers
class fibNumbers{
static int fn(int n){
int x=0, y=1, z;
if(n == 0)
return x;
for(int i=2; i<=n; i++){
z = x + y;
x = y;
y = z;
}
return y;
}
public static void main (String args[]){
int n = 6;
System.out.println(fn(n));
}
}Output : 8
Using Direct Formula
Here we’ll directly use the formula to find the nth Fibonacci number i.e.
Fn = ( ( ( (√5 + 1) / 2) ^ n) / √5)
Time Complexity : O(1)
Space Complexity : O(1)
C++ Program
#include<bits/stdc++.h>
using namespace std;
int fn(int n){
double gr = (1 + sqrt(5)) / 2;
return round(pow(gr, n) / sqrt(5));
}
int main (){
int n = 6;
cout<<fn(n);
return 0;
}Output : 8
Java Program
import java.util.*;
class fibNumbers{
static int fn(int n){
double gr = (1 + Math.sqrt(5)) / 2;
return (int) Math.round(Math.pow(gr, n) / Math.sqrt(5));
}
public static void main (String args[]){
int n = 6;
System.out.println(fn(n));
}
}Output : 8