Earlier I mentioned a recursive function to detect palindromes that I needed to create for my Python computer science course. I was really happy when I grasped the usefulness and power of recursive functions from the lecture and was able to apply it so quickly to palindromes. The class also wrote recursive functions to calculate Fibonacci numbers as well as paying off credit cards.
Shortly after learning all this wonderful knowledge, my algorithms course started and the instructor started the course by explaining the importance of choosing the best algorithm. He then demonstrated the naive algorithm of using a recursive function to solve for Fibonacci numbers. This was rather eye-opening since I just learned recursive functions and applied it to Fibonacci.
To be honest, I sort of suspected problems with using a recursive function for Fibonacci numbers only because I tried to solve it for the 100th number on my MacBook Pro and it felt like the application hung. I don't believe I actually got a number. I think I just quit the application.
For fun, I looked back at the recursive function I created for detecting palindromes and realized that although the function is fine and won't have the same issues as Fibonacci, there are other algorithms to detect palindromes in Python as well. I, personally, prefer the new algorithm over the recursive function. It's intuitive, simple, and a lot less complex. Of course, the assignment was to write recursive functions. I suspect it never meant to suggest using a recursive function to detect palindromes.
Fibonacci Sequence Algorithms - Python
I found this so fascinating that I wanted to write down my thoughts on the Fibonacci sequence and show two different algorithms and the performance difference. I realize there are other methods of calculating Fibonacci numbers, but I wanted to work with a couple of functions that I think really drive home the point.
Below I have two functions that calculate Fibonacci numbers. The first is a recursive implementation, and the second one is an alternative 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!