Day twenty seven: fibonacci

October 22, 2015

Always had troubles remembering the 1200th position of the Fibonacci sequence? Let the app of today help you out! Insert the desired position and the app will provide the solution!

live demo

Delving farther into computer science I wanted to create an app that computes the number at the desired position in the Fibonacci sequence. What is Fibonacci you might ask. It sounds delicious but, sadly, it’s not edible. What is it then? To understand it will help to know the backstory.

backstory

Leonardo Fibonacci had two rabbits. A male and a female. After a month they grew up to be fine adults. Doing what rabbits do best. They had two offspring. Again, a male and a female. These baby rabbits were grown up after a month and after committing adultery. Had two offspring. Surprisingly enough, A male and a female! Fibonacci wanted to know how many rabbits there were at any given month.

Assuming rabbits never die and after every month all offspring were couples of male and female. Fibonacci realized that the total amount of rabbits would be the sum of rabbits of the previous 2 months.

//Where n is the desired month
f(n - 1) + f(n - 2)

rabbit That’s right mister rabbit. The Fibonacci sequence is a way to compute how fast you breed. Pretty neat , huh!

implementing the algorithm

In the previous section we learned that in order to get the solution. We need the sum of the last two positions. Try to think how to implement this? At first glance this can be a bit daunting. However, let’s ignore the big picture and start off with the solution at the position 0 and 1.

function fibonacci(n) {
  if (n === 0 || n === 1) {
    return n;
  }
}

fibonacci(0)
// 0
fibonacci(1)
// 1

If the user requests the solution at position 0 or 1. We have it covered, awesome! However, when anything higher is requested. We are doomed. How can we say no to this cute little rabbit?! cute rabbit

We have to solve it for 2 and higher too. In order to do that we need to modify our fibonacci function to allow that. It should look at the previous two positions and return the sum. Looking at our function that is actually straight forward.

function fibonacci(n) {
  if (n === 0 || n === 1) {
    return n;
  }

  return fibonacci(n - 1) + fibonacci(n - 2);
}

fibonacci(0)
// 0
fibonacci(1)
// 1
fibonacci(2)
// 1

Woah, Slow down! What is this sorcery we added! Calling the same function again. Does that even work?! Yes, my dear reader, this is called recursion. To understand it. You can either read the terribly long wikipedia article or google on recursion and keep clicking on the “Did you mean” link. You will get the idea. Let’s look at the use of recursion in this particular case.

recursion

Assume that n is equal to 2. When we call the function. we return the equivalent of:

fibonacci(1) + fibonacci(0)

Looking back at our fibonacci implementation. When called with 1 the function returns 1. When called with 0 the function returns 0. Knowing that, now we return the equivalent of:

1 + 0

The function keeps calling itself until it returns an integer. Then it keeps summing until the top level gets resolved. Recursion is neat, huh! Computing it this way leads to a different problem. When the user requests a high position like 1000. The function gets called … a lot. Let’s look on how to solve this!

big numbers

We would like to limit the amount of calls that our fibonacci function has to make. To do this we can implement a cache. This is basically an array which keeps all the positions that are already computed.

Talk is cheap. Show me the code!

// Introducing the cache in the form of a list
    var cache = [];

    function fibonacci(n) {
      if (n === 0 || n === 1) {
      	return n
      } else {
         // Looks the number up in the cache
         // When it is not in there. Compute what it should be and place it in the cache
         cache[n] = cache[n] || fibonacci(n - 1) + fibonacci(n - 2);
         return cache[n];
      }
    };

That is all there is to it! Now without much effort the 1200th position in the sequence can be computed!

Thank you for reading and don’t forget to leave a star on the repo.

Comments