Fibonacci sequence is a very interesting problem for computer science beginners. Recruiters often ask to write the Fibonacci sequence algorithm using recursion and dynamic programming and find their time complexity.
There are two popular ways to find Fibonacci sequence or
nth Fibonacci number.
- Fibonacci sequence Algorithm using Recursion (Slow)
- Fibonacci sequence algorithm using Dynamic programming (Fast)
Naive Fibonacci algorithm using recursion
This is a popular yet slow algorithm to find Fibonacci numbers.
We all hear the term that recursion has its own cost in programming. This is very true in this scenario. It is hard to optimize a recursive solution of the Fibonacci algorithm.
Here is the Fibonacci algorithm using recursion.
function fibonacci(n): if(n<=1): return n else: return fibonacci(n-1)+fibonacci(n-2)
Fibonacci algorithm using recursion time complexity.
F(n) = F(n-1)+F(n-2)
Why Recursion algorithm to find the Fibonacci number is Slow?
Here is a diagram which illustrates the reason.Open Image
Fibonacci recursion tree
This is the visual representation of the recursive algorithm.
Many of the items like
F(n-3)in this example are evaluated multiple times. This is a problem with recursion.
This makes the algorithm very slow because the same calculation is repeated multiple times. Even for small numbers like 100, the recursive algorithm will fail to give timely output.
There is an alternative to this which is much more fast.
Fast Fibonacci algorithm using Dynamic programming
The above algorithm is very slow and not very useful in real situations. There is an alternative to this is which is fast and efficient.
Fibonacci sequence algorithm using dynamic programming is an optimization over plain recursion.
In the recursive example, we see that the same calculation is done multiple times which increase the total computational time.
Dynamic programming solves this problem because it stores the previous calculations safe for future use.
Dynamic programming is very easy as compared to recursion and we all use it most of the times.
Fibonacci numbers algorithm using dynamic programming.
fib = [0, 0, 0, 0, ....n] fib = 0 fib = 1 for i=2 to n: fib[i] = f[i-1]+f[i-2]
The time complexity of this algorithm to find Fibonacci numbers using dynamic programming is O(n).
The reason for this is simple, we only need to loop through n times and sum the previous two numbers.
Here is a visual representation of how dynamic programming algorithm works faster.Open Image
Dynamic programming stores previously calculated elements
Here it is clear that this approach stores previous computed elements and use them to find new one.
Conclusion: Fibonacci using Recursion vs Dynamic Programming
As a beginner we only think to solve a problem without any efficiency in mind, this may be good because we are developing problem-solving skills.
However, we must try to create an optimized solution for every algorithm. This will not only enhance our skills but also make us ready to solve problems in the real world.
You should always try to write the algorithm using dynamic programming to find Fibonacci numbers because it is fast and efficient.
At last, we should know that there are two types of programmers.
Typewriters: They only focus to solve a problem with no efficiency or scalability in mind, having no interest or creativity and money is their only motivation.
Elite developers: They are the ones who write the code with performance in mind. They write, think, optimize, think again, optimize more, are passionate coders and can help to change the world.
Don’t be a typewriter, be an elite developer.