# 5 Ways of Fibonacci in Python – Best way!

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

 Fib(n=15000) loops recursion generators memoization memoization as decorator 45 87 58 44 43 47 88 58 42 42 51 92 60 44 43 43 87 58 42 43 48 92 61 42 44 45 87 59 43 44 44 85 57 42 44 44 87 62 43 43 48 86 59 42 43 45 91 61 45 45 46 88.2 59.3 42.9 43.4   (Avg)

Takeaways:

• 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… 🙂

## 2 thoughts on “5 Ways of Fibonacci in Python – Best way!”

1. No Name says:

THX

2. Tomasz Stempkowicz says:

The best (fastest) way is not to use recursion or loops. Example of very goog solution which works fast for big numbers:

from numpy import matrix

def fib(n):
return (matrix(
‘0 1; 1 1’ if n >= 0 else ‘-1 1; 1 0’, object
) ** abs(n))[0, 1]

This site uses Akismet to reduce spam. Learn how your comment data is processed.