Program to find n’th Fibonacci number
Write a program to calculate the nth Fibonacci number where n is a given positive number.
Fibonacci’s sequence is characterized by the fact that every number after the first two is the sum of the two preceding ones. For example, consider the following series:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … and so on.
As we can see above, each subsequent number is the sum of the previous two numbers. The starting point of the sequence is sometimes considered 1, resulting in the first two numbers in the Fibonacci sequence as 1 and 1.
The following recurrence relation defines the sequence Fn of Fibonacci numbers:
F{n} = F{n-1} + F{n-2} with base values F(0) = 0 and F(1) = 1.
Following is the naive implementation in C, Java, and Python for finding the nth member of the Fibonacci sequence:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <stdio.h> // Function to find the nth Fibonacci number int fib(int n) { if (n <= 1) { return n; } return fib(n - 1) + fib(n - 2); } int main() { int n = 8; printf("F(n) = %d", fib(n)); return 0; } |
Output:
F(n) = 21
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Main { // Function to find the nth Fibonacci number public static int fib(int n) { if (n <= 1) { return n; } return fib(n - 1) + fib(n - 2); } public static void main(String[] args) { int n = 8; System.out.println("F(n) = " + fib(n)); } } |
Output:
F(n) = 21
Python
We can easily convert the above recursive program into an iterative one. If we carefully notice, we can directly calculate the value of F(i) if we already know the values of F(i-1) and F(i-2). So if we calculate the smaller values of fib first, we can easily build larger values. This approach is also known as the bottom-up approach and widely used to solve dynamic programming problems.
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <stdio.h> // Function to find the nth Fibonacci number int fib(int n) { if (n <= 1) { return n; } int previousFib = 0, currentFib = 1; for (int i = 0; i < n - 1; i++) { int newFib = previousFib + currentFib; previousFib = currentFib; currentFib = newFib; } return currentFib; } int main(void) { int n = 8; printf("F(n) = %d", fib(n)); return 0; } |
Output:
F(n) = 21
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Main { // Function to find the nth Fibonacci number public static int fib(int n) { if (n <= 1) { return n; } int previousFib = 0, currentFib = 1; for (int i = 0; i < n - 1; i++) { int newFib = previousFib + currentFib; previousFib = currentFib; currentFib = newFib; } return currentFib; } public static void main(String[] args) { int n = 8; System.out.println("F(n) = " + fib(n)); } } |
Output:
F(n) = 21
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
# Function to find the nth Fibonacci number def fib(n): if n <= 1: return n previousFib = 0 currentFib = 1 for i in range(n - 1): newFib = previousFib + currentFib previousFib = currentFib currentFib = newFib return currentFib if __name__ == '__main__': n = 8 print('F(n) =', fib(n)) |
Output:
F(n) = 21
The time complexity of the above iterative solution is O(n) since it contains a loop that repeats n-1 times, but it only takes constant space, in contrast to the recursive approach, which requires O(n) space for recursion (call stack) and exponential time as many subproblems are recalculated repeatedly. We can also improve the time complexity of the recursive approach by saving values that have already been calculated. This approach is discussed below in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <iostream> #include <unordered_map> using namespace std; // Function to find the nth Fibonacci number int fib(int n, auto &lookup) { if (n <= 1) { return n; } // if the subproblem is seen for the first time if (lookup.find(n) == lookup.end()) { lookup[n] = fib(n - 1, lookup) + fib(n - 2, lookup); } return lookup[n]; } int main() { int n = 8; unordered_map<int, int> lookup; cout << "F(n) = " << fib(n, lookup); return 0; } |
Output:
F(n) = 21
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
import java.util.HashMap; import java.util.Map; class Main { // Function to find the nth Fibonacci number public static int fib(int n, Map<Integer, Integer> lookup) { if (n <= 1) { return n; } // if the subproblem is seen for the first time lookup.putIfAbsent(n, fib(n - 1, lookup) + fib(n - 2, lookup)); return lookup.get(n); } public static void main(String[] args) { int n = 8; Map<Integer, Integer> lookup = new HashMap<>(); System.out.println("F(n) = " + fib(n, lookup)); } } |
Output:
F(n) = 21
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
# Function to find the nth Fibonacci number def fib(n, lookup): if n <= 1: return n # if the subproblem is seen for the first time if n not in lookup: lookup[n] = fib(n - 1, lookup) + fib(n - 2, lookup) return lookup[n] if __name__ == '__main__': n = 8 lookup = {} print('F(n) =', fib(n, lookup)) |
Output:
F(n) = 21
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)