Program to find n’th Fibonacci number

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 Fn 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 –

 

Download   Run Code

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.

 

Download   Run Code

 

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 here.
 

 
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

Notify of
avatar
wpDiscuz