# Recursion & Memoization In Python

4 min readRecursion can be a dirty word in programming. It gets a bad wrap for good reasons like stack overflows and infinite loops. In this post we will look at the Fibonacci sequence and how we can apply recursive concepts to solve it. We will then look at how horribly inefficient this solution is and how the concept of memoization can drastically improve that efficiency.

## The Problem

The Fibonacci sequence, in case you have not heard of it, is a mathematical sequence where a number is the sum of the two previous numbers before it.

So looking at these numbers 1 is the sum of `0 + 1`

and 2 is the sum of `1 + 1`

and so on and so forth.

## Enter Recursion

Recursion is when we call a function from within itself. With recursion we need to think in terms of our terminating case first, so at what point should our recursive function call end. We think in these terms to avoid entering an infinite loop since we will be calling the function from inside itself. In the case of fibonacci when we have made it to the last two numbers, 0 and 1, we have made it to our terminating case. We can check for this through the following conditional:

So our function will start off looking as:

Now since we know that fibonacci is the sum of the two previous numbers we can call our `fib()`

and add the two calls together where we are taking one less and two less `n`

as the inputs for each iteration:

## Executing Fibonacci

When we run our `fib`

function we can see that it works with no issues with smaller numbers. Running `fib(8)`

returns relatively quickly; however if we run `fib(40)`

we will be waiting for a hot minute for the return value. This is due to the fact that we are processing a lot of the same computation over and over again. For example let’s look at `fib(5)`

:

So looking at the above diagram we can see that we run the computation of `fib(3)`

twice as well as other instances. If we have ran and know the value of this computation already it becomes redundant to process it over an over again.

## Enter Memoization

Memoization is a manner in which we can cache our results and then check to see if we have seen that function call before.

Now when using memoization with our `fib()`

our diagram changes to look like the following:

We get this instead because we have stored the return value from `fib(n)`

at the specified key in our cache.

## Using our memoization function

There are two ways to use this function in Python. We can just supply `fib`

to it and reassign `fib`

or we can use the *decorators* feature:

Now when running `fib(40)`

we see a nearly instant return in the terminal just like we had seen before with lower input values. Memoization is a great way to increase the performance of a recursive function.

### Related Articles

## Python Scripting In iTerm2

How to use the Python Scripting API in iTerm2 to open several tabs and execute commands in those tabs.

## Writing A Connect Four Game Reader In Python

Writing a program that will read moves and populate a game board for the popular game Connect Four using Python.

## Getting Started With Python3

Installation and setup of Python3 on macOS & development with Visual Studio Code.

## Building A Black Jack Advice Generator With Python

How to build a simple black jack advice generator using Python.

Cody is a Christian, USN Veteran, Jayhawk, and an American expat living outside of Bogotá, Colombia where he works as a Senior Frontend Developer for WAO Fintech.