The Rabbit Hole of Fibonacci Sequences, Recursion and Memoization

Ok, prepare yourself for the literal rabbit hole of my Tuesday night….

First, JP led me to Memoization, which then led me to recursion, which led to Fibonacci Sequences, which obviously and inevitably led me to rabbits…

I am warning you….

Fibonacci Sequence

What is the Fibonacci Sequence? It is a series of numbers in which each number is the sum of the two preceding numbers.

This is a very famous set of numbers and was found in the 12th century by a mathematician named Leonardo Fibonacci. This sequence was first thought of when Fibonacci was pondering the question of rabbit reproduction? Weird/Random, I know. Stick with me.

Basically, the problem assumes the following conditions:

  • Begin with one male rabbit and female rabbit that have just been born.
  • Rabbits reach sexual maturity after one month.
  • The gestation period of a rabbit is one month.
  • After reaching sexual maturity, female rabbits give birth every month.
  • A female rabbit gives birth to one male rabbit and one female rabbit.
  • Rabbits do not die.

Side Note — Fibonacci Spiral

A Fibonacci spiral is a series of connected quarter-circles drawn inside an array of squares with Fibonacci numbers for dimensions. The squares fit perfectly together because of the nature of the sequence, where the next number is equal to the sum of the two before it. Any two successive Fibonacci numbers have a ratio very close to the Golden Ratio, which is roughly 1.618034. The larger the pair of Fibonacci numbers, the closer the approximation. The spiral and resulting rectangle are known as the Golden Rectangle. The sequence is also closely related to a famous number called the golden ratio. You can find this series of numbers in the turns of natural spirals, in plants, and in the family tree of bees.

Recursion

Ok, back to how all this related to the code. So we have all heard people talk about recursion, and that it is when a function calls itself and that it makes programs more efficient. But why? And how? And when would you use this? Lets take a dive using the Fibonacci Sequence as our example!

Below is an example of how a given index of the Fibonacci Sequence would be calculated. Notice that it is calling the fibonacci sequence on itself until it gets down to the base case of the series, as each proceeding number depends on the ones before it, then calculates back up to the index desired.

function fibonacci(n) {
if (n === 0 || n === 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}

This function performs well for small values of “n”. However, performance quickly degrades exponentially as “n” increases. This is because the two recursive calls repeat the same work. You can see these repetitive calls in the recursion tree below.

You can see that F(1) gets calculated three times, F(2) 5 times, F(3) 3 times, F(4) twice….…

In comes Memoization….

Memoization

The idea of Memoization is that it is a programming technique which attempts to increase a function’s performance by caching its previously computed results. Basically, every time that a Fibonacci index gets calculated, the result can be stored in an outside object so that the recursive function can access it and use an already calculated result in its future calculations since they are all dependent upon each other.

Side Note: The definition of cache is “a temporary storage space or memory that allows fastaccess to data”. One misconception, albeit mostly on my end, is that caches are only through the browser and in the form of things like cookies, tokens, etc. However, the term refers to anything in computing where things are saved for later use to speed up processing.

“Memoized functions store a cache which is indexed by their input arguments. If the arguments exist in the cache, then the cached value is returned. Otherwise, the function is executed and the newly computed value is added to the cache.”

Let’s take a look at the code below and note that we are storing calculated results in memo.

  1. It establishes its caching object, memo.
  2. It first checks if the fibonacci index has been calculated before and saved in memo.
  3. If it is, then it uses that value in the recursive function.
  4. If it is not, it then continues to calculate the next term in the fibonacci sequence as before, while also saving it into the cache object for future use.
var fibonacci = (function() {
var memo = {};

function f(n) {
var value;

if (n in memo) {
value = memo[n];
} else {
if (n === 0 || n === 1)
value = n;
else
value = f(n - 1) + f(n - 2);

memo[n] = value;
}

return value;
}

return f;
})();

This code allows the function to reference the previously calculated values. Let’s take a look back at our recursion tree, but with memoization. You can see we are now able to eliminate many of our calculations.

This is the magic of Memoization!

Unfortunately, most problems are more complex and functions have more than just 1 argument. This means there is not a simple key value pair for each calculation to be stored in. This can be dealt with in two ways. The most common being to create a hierarchy of objects(like a nested hash). The less common being a single cache object which is indexed by a combination of all of the function’s arguments. Under this approach, the arguments are transformed into an array and then used to index the cache. Both of these methods are detailed in the last resource below. Take a look!

In summary, memoization is beneficial when a recursive function is repeating multiple calculations because and it can store those results in an object and pull them when needed, instead of completely recalculating them. If it is a short function that isn’t used often and calculation times are fast, then memoization may not be necessary.

Resources: