ternative using a list. The recursive implementation is pretty well known, but possibly only to show how to write recursive functions.
def fib_recursive(n): if n < 2: return n return fib_recursive(n - 1) + fib_recursive(n - 2) def fib_list(n): if n < 2: return n sequence = [0, 1] for i in range(2, n + 1): sequence.append(sequence[i - 1] + sequence[i - 2]) return sequence[n] print fib_recursive(30) # 832040 print fib_list(30) # 832040
Solving for 30th Fibonacci Number
My goal is to roughly compare the performance of these two algorithms at calculating a couple of Fibonacci numbers. I don't know what to expect, so I randomly chose to find the 30th Fibonacci number. When I call both functions they return the same number and I verified the 30th number of Fibonacci is 832040. However, there is a slight pause on my MacBook Pro when running the recursive algorithm whereas the list version returns immediately.
I profiled the code using the profiler in PyCharm. The call graph looks like this.
The green path represents the better performing function. The list algorithm is clearly faster. It runs 1 time and essentially takes no time to solve the problem. The recursive function, on the otherhand, is called over 2.5 million times and solves it a little under a second. The 719ms doesn't strike me as a big deal, but 2.5+ million function calls is really unexpected.
Solving for 38th Fibonacci Number
I tried running 60, 50, and 40, and the application felt like it hung. I was hoping for a response within 30sec. Again, I am new at this so I am not sure how long it takes and what is a reasonable time to wait. I tried 38 and the program finished. Here is the call graph for finding the 38th Fibonacci number using both algorithms. Again, the list algorithm came back pretty much immediately while the recursive function took some time.
This blows my mind! Assuming I am reading this call graph correctly, the recursive function called itself 126 millon times?! Now I know why solving for the 100th Fibonacci number never finished. And look at the performance of the list algorithm. It didn't even break a sweat!
The recursive function in Python for solving Fibonacci numbers seems so innocent until you try it for yourself and look at a profiler. I can really appreciate the importance of a good performing algorithm when dealing with a lot of data and complex math functions. I am going to seek out more examples like this, because I think it's pretty cool!
Posted by Koder Dojo
Thanks for visiting Koder Dojo. I hope the article on solving for Fibonacci numbers using Python was entertaining and meaningful. I just started learning Python, and am enjoying it. I'll be writing a lot of beginner tutorials based on the 4 online courses I am taking: computer science, algorithms, data structures, and cryptography. I am a professional C# ASP.NET MVC Developer so I will be talking about the new .NET Core and ASP.NET Core frameworks as well. I hope you keep visiting!