As I continue to take computer science and algorithms courses, the naieve, recursive function to calculate Fibonacci numbers is used to illustrate a lot of programming techniques. The main issue with the recursive algorithm to calculate Fibonacci numbers is that as the numbers get big, the recursive algorithm calculates several Fibonacci numbers over and over again. Memoization, which I will talk about here, helps reduce the number of recursive calls by storing previous values.

Python Function Using Memoization to Solve for Fibonacci Numbers

Here is the python function I wrote that uses memoization to help speed up the naieve recursive solution to solving for Fibonacci numbers. I will talk about memoization and local functions next.

def fib(n):
    def fib_memo(n, m):
        """
        Find the n'th fibonacci number. Uses memoization.

        :param n: the n'th fibonacci number to find
        :param m: dictionary used to store previous numbers
        :return: the value of the n'th fibonacci number
        """

        if n in m:
            return m[n]

        answer = fib_memo(n - 1, m) + fib_memo(n - 2, m)
        m[n] = answer
        return answer

    m = {1: 1, 2: 1}
    return fib_memo(n, m)


print(fib(50))   # 12586269025
print(fib(60))   # 1548008755920
print(fib(100))  # 354224848179261915075

Memoization

To quote Wikipedia, "In computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again." In this case, memoization will alleviate the need to re-solve already solved Fibonacci numbers.

In this case, I am using a Python dictionary (m) to store nth Fibonacci numbers. The dictionary will initially contain the values of the first 2 Fibonacci numbers, 1 and 2. The 1st Fibonacci number is 1. The second Fibonacci number is also 1.

m = {1: 1, 2: 1}

I will continue to add to this Python dictionary each time I solve another Fibonacci number. Therefore, when I solve the 3rd, 4th, and 5th Fibonacci numbers, they will be stored in there as well.

m = {1: 1, 2: 1, 3: 2, 4: 3, 5: 5 ... }

To alleviate having to re-solve Fibonacci numbers over and over, I check to see if the number has already been solved and is in the Python dictionary first. If so, I return the value from the dictionary and do not solve for it again.

if n in m:
    return m[n]

This small change makes a huge performance impact for larger numbers by reducing the number of recursive calls.

Local Functions

Local functions are the same as nested functions, which are just functions defined within a function. They are extremely helpful in the case of recursive functions when you may need a bit of helper code that only needs to run once before entering or after leaving the function to be called recursively. In this case I use local functions to initialize the Python dictionary used for memoization. I could also add a bit of parameter validation and other features, too. The initialization code in this case is just one line to initialize the Python dictionary before calling into the recursive function.

m = {1: 1, 2: 1}

One could consider creating the memoization dictionary as a global variable and initializing this dictionary only once, and keeping the values in it for the life of the application. This way subsequent calls to calculate new Fibonacci numbers get faster and faster because of all the values that have accumulated in the dictionary by previous calls. I tend to shy away from the use of global variables, but this would be an interesting change if one is calculating a lot of larger Fibonacci numbers on the fly and performance is absolutely critical.

Conclusion

Memoization, which is just a form of caching, is a really cool performance technique to avoid re-solving overlapping subproblems. In this example, the number of recursive calls memoization helps avoid for large Fibonacci numbers is absolutely amazing.

Posted by Koder Dojo

I am a freelance C#, ASP.NET MVC Developer learning Python. I am taking several online computer science, algorithms, cryptography, and now data science courses using Python. It is a wonderful learning experience and I am journaling my adventures on this website. I am eager to meet new people and share my experiences. If you are on twitter, please add me. I am @KoderDojo.

Related Posts: