Fibonacci Sequence: The Recursive Algorithm
When people are introduced to programming and to the recursion paradigm, the computation of the Fibonacci sequence is a common exercise used to establish such concepts.
The Fibonacci sequence corresponds to a pattern of integers in which a Fibonacci number is given by summing the previously two Fibonacci numbers. For example: 1, 1, 2 (1 + 1), 3 (2 + 1), 5 (3 + 2), 8 (5 + 3), 13 (8 + 5), 21 (13 + 8), 34 (21 + 13), 55 (34 + 21), 89 (55 + 34), 144 (89 + 55), ...
When asked to implement a recursive version of Fibonacci, the first thing that comes to mind, and that most people do, is this:
Using the above implementation, it is obvious that the calculation of the Fibonacci sequence is very inefficient and is not realistic for more than 35 Fibonacci numbers.
Fibonacci Sequence: Another Recursive Algorithm
The main idea of this algorithm, is to keep track of the two previously computed Fibonacci numbers. This way, the new algorithm will only perform N recursive operations, O(N), while the previous solution has a performance of O(2^N).
Comparing Performances
If we compare the performance of both algorithms, we can see that the first recursive algorithm proposed can only be used for Fibonacci sequences bellow 35. After this, the algorithm becomes extremely inefficient. The other recursive algorithm proposed, however, is able to perform the Fibonacci sequence very efficiently, running in linear time. We can see drastic differences when computing the Fibonacci sequence for N = 45. It takes, on average, 3.35 minutes for the typical recursive algorithm to provide a solution, whereas the optimized recursive method takes only 6 milliseconds to perform the very same operation.
 |
 |