For appreciating this post, I request you to go through 5 Ways of Fibonacci in Python post of mine, where I have explained 5 different ways by which you could write code for finding nth Fibonacci number. At the end of the post, I had promised you that I would come up with performance measurements for each of these ways and conclude on whats the best way; So, here I am!
When I used all five ways to calculate 15000th Fibonacci number, and calculated the time taken by each of these methods for 10 iterations, this is what I got
|loops||recursion||generators||memoization||memoization as decorator|
- Looping technique seems pretty reasonable
- Recursion is hell.. lets consider we need to find fib(5). Now, fib(5) = fib(4) + fib(3) and fib(4) = fib(3) + fib(2) and so on.. Now in this case, fib(3) is calculated twice, which is redundant. Hence the increased time as depicted in the table above.
- Generators help in creating iterators and avoid the issues with recursion, but are slightly heavy as the function is re-entered over and again
- Memoization ensures the calculated numbers like fib(3) in case of recursion and hence are faster
- Decorators adds a slight overhead in terms of program flow switching between decorator to the actual function and hence slightly slower than Memoization without decorators
So the clear winner is Memoization on a function written with a for loop…