Memoizing Fibonnaci
Published: 2021-09-01 05:42:29

As programmers, we often want our code to be [DRY](https://en.wikipedia.org/wiki/Don%27t_repeat_yourself) - written with the fewest characters possible. However, as anyone who has been stuck in a death loop of recursion can attest, even syntactically DRY bits of code can cause us problems:

```
def death_loop(num)
    return death_loop(num + 1)
end
``` 

![error gif](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/31gxhu4wrsphraxg1wi6.gif)

But what if our code *needs* to be recursive? Sometimes we need to write functions that call on themselves. 

![austin powers](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9gjav8mw1lljhjz0qlp8.gif)

##Enter memoization. 

>Memoization is an [optimization technique](https://en.wikipedia.org/wiki/Memoization) 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 other words, memoization offers programmers the chance to be DRY *functionally* as well as syntactically, reducing the number of times a function is called by our program. 

##How it works

We will define a function. Let's call it compute(input)
In the body of the function, compute(input) will...

1. Check if this precise input has been computed before (using a `memo` variable we will define below).
2. If this input has been computed before, return `memo` and save the program needless computing! 
3. If this input has *not* yet been computed, perform computations.
4. Save result of the computations to `memo`.
5. Return the result.

Let's take a look at a case that's a little less common and a little more interesting than a recursive death loop.

## Enter Fibonacci

If you were an enthusiast of calculus or the illuminati in high-school, you may have encountered that most famous example of recursive sequences, the [Fibonacci Numbers](https://en.wikipedia.org/wiki/Fibonacci_number). Put simply, each number in the sequence (integers only) is equal to the sum of the two preceding numbers, starting with the bottom two numbers of 0 and 1.

*0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... and on to infinity*. 

![Fibonacci gif](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zkpa0q6jm86wiuxuf8pe.gif)

Let's take a look at Fibonacci in code. Written in Ruby without memoization, our Fibonacci code might look something like this: 

![ruby fibonacci](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hd8qnsnab04gq4vta566.png)

This solution works great for small numbers, but comes with  some serious [time complexity](https://towardsdatascience.com/essential-programming-time-complexity-a95bb2608cac) costs. As the input increases, the "sub-calls" of our function grow exponentially, as illustrated by a [recursion tree](https://www.interviewcake.com/concept/java/memoization):


![recursion tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/r2dmlwlveic9xd07i88p.png)
 
To save on these costs, we can define a Memoize class in Ruby and use a @memo variable to cache our completed computations. 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5jhq35mtmaxr5gmgev35.png)

Benissimo. Fibonacci memoized.





### Sources
- [Don't Repeat Yourself](https://en.wikipedia.org/wiki/Don%27t_repeat_yourself)
- [Memoization](https://en.wikipedia.org/wiki/Memoization)
- [Fibonacci Numbers](https://en.wikipedia.org/wiki/Fibonacci_number)
- [Memoization](https://www.interviewcake.com/concept/java/memoization)
- [Time complexity](https://towardsdatascience.com/essential-programming-time-complexity-a95bb2608cac)



### Recommendations for Further Learning
- [5 Simple Steps for Solving Any Recursive Problem](https://www.youtube.com/watch?v=ngCos392W4w&t=613s)
- [The Rubyist's Guide to Memoization](https://www.honeybadger.io/blog/rubyist-guide-to-memoization/)
- [Understanding recursion, memoization, and dynamic programming: 3 sides of the same coin](https://medium.com/swlh/understanding-recursion-memoization-and-dynamic-programming-3-sides-of-the-same-coin-8c1f57ee5604)
- [Bottom-up Fibonacci: Visualization of JS code execution](https://www.youtube.com/watch?v=22VM0onqAMU)