Write a program to calculate n’th Fibonacci number where n is a given positive number.

Fibonacci sequence is characterized by the fact that every number after the first two is the sum of the two preceding ones. For example, consider below sequence –

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 as 1, which will result in the first two numbers in the Fibonacci sequence as 1 and 1.

The sequence F_{n} of Fibonacci numbers is defined by the recurrence relation:

`F{n} = F{n-1} + F{n-2}`

with base values `F(0) = 0`

and `F(1) = 1`

.

Below is naive implementation for finding the n’th member of the Fibonacci sequence –

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 n'th Fibonacci number int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } // main function int main() { int n = 8; printf("n'th Fibonacci number is %d", fib(8)); return 0; } |

`Output:`

n’th Fibonacci number is 21

We can easily convert above recursive program to 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, then we can easily build larger values from them. This approach is also known as the bottom-up approach to and vastly used to solve Dynamic Programming problems.

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 |
#include <stdio.h> // Function to find 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) { printf("%d", fib(8)); return 0; } |

The time complexity of 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 again and again (refer this post). We can also improve time complexity of recursive approach by saving values that have already been calculated. This approach is discussed below:

## 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 |
#include <iostream> #include <unordered_map> // Function to find nth Fibonacci number int fib(int n, auto &lookup) { if (n <= 1) return n; // if sub-problem 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; std::unordered_map<int, int> lookup; std::cout << fib(n, lookup); return 0; } |

`Output:`

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 27 28 |
import java.util.HashMap; import java.util.Map; class Fibonacci { // Function to find nth Fibonacci number public static int fib(int n, Map<Integer, Integer> lookup) { if (n <= 1) { return n; } // if sub-problem is seen for the first time if (!lookup.containsKey(n)) { lookup.put(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(fib(n, lookup)); } } |

`Output:`

21

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply