Memoization visualized through recursive Fibonacci

ProgrammingJul 2021

Part of learning to program is to progressively develop the sensibility to stop writing the same things over and over again, and know when to abstract portions of code that run multiple of times into their own dedicated container; a container I can reference to multiple times in the future.

Good programming lies in a person’s ability to identify and work with ever more sophisticated versions of this idea of abstraction, optimization, and simplification. While also keeping in mind the program’s efficiency (how many steps are taken) and how much space it requires (space meaning literal memory). The careful balance of these forces is the life-long learning experience of programming.

One of the tools used to achieve this is the idea of memoization. In short, memoization is the idea of storing the result of a procedure — a piece of code — so that if, while the program is being run, that procedure needs to run again and again to yield the same result, I can rather store it somewhere and access that same result as many times as needed without having to run the code again.

Calculating a Fibonacci number — a number that results from the sum of its previous two counterparts — is a good example to demonstrate the utility of memorization. In essence, the Fibonacci sequence:

The process of traversing through this sequence is most efficiently done using a recursive function.

But, this recursive solution even though simple in design, creates a multiple function calls on the same number to yield the same result. Take fib(5):

In a simple fib(5), there are multiple calls on 3, 2, and 1. Now imagine calling fib(546731). This is where memoization comes in. To reiterate, memoization is the idea of storing the result of a function call for later use. This can be done with a simple key/value dictionary where, every time I call fib on a number for the first time, I’ll store the number and its result in the dictionary for later.

That means that each number will, now, only be called once. In all future calls after the first one, the fib function will use the value already stored without running itself again.

In a nutshell, that’s it. The idea of memoization isn’t exclusive to Fibonacci. It rather comes down to grasping it as an approach to be used in problems where  the same piece of code is being run again and again to yield the same result.

No items found.