Fibonacci numbers

back to the lesson

The sequence of Fibonacci numbers has the formula F_n = F_n-1 + F_n-2. In other words, the next number is a sum of the two preceding ones.

First two numbers are 1, then 2(1+1), then 3(1+2), 5(2+3) and so on: 1, 1, 2, 3, 5, 8, 13, 21....

Fibonacci numbers are related to the Golden ratio and many natural phenomena around us.

Write a function fib(n) that returns the n-th Fibonacci number.

An example of work:

          function fib(n) { /* your code */ }

alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757
        

P.S. The function should be fast. The call to fib(77) should take no more than a fraction of a second.

The first solution we could try here is the recursive one.

Fibonacci numbers are recursive by definition:

function fib(n) {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // will be extremely slow!

…But for big values of n it’s very slow. For instance, fib(77) may hang up the engine for some time eating all CPU resources.

That’s because the function makes too many subcalls. The same values are re-evaluated again and again.

For instance, let’s see a piece of calculations for fib(5):

          ...
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
...
        

Here we can see that the value of fib(3) is needed for both fib(5) and fib(4). So fib(3) will be called and evaluated two times completely independently.

Here’s the full recursion tree:

We can clearly notice that fib(3) is evaluated two times and fib(2) is evaluated three times. The total amount of computations grows much faster than n, making it enormous even for n=77.

We can optimize that by remembering already-evaluated values: if a value of say fib(3) is calculated once, then we can just reuse it in future computations.

Another variant would be to give up recursion and use a totally different loop-based algorithm.

Instead of going from n down to lower values, we can make a loop that starts from 1 and 2, then gets fib(3) as their sum, then fib(4) as the sum of two previous values, then fib(5) and goes up and up, till it gets to the needed value. On each step we only need to remember two previous values.

Here are the steps of the new algorithm in details.

The start:

          // a = fib(1), b = fib(2), these values are by definition 1
let a = 1, b = 1;

// get c = fib(3) as their sum
let c = a + b;

/* we now have fib(1), fib(2), fib(3)
a  b  c
1, 1, 2
*/
        

Now we want to get fib(4) = fib(2) + fib(3).

Let’s shift the variables: a,b will get fib(2),fib(3), and c will get their sum:

          a = b; // now a = fib(2)
b = c; // now b = fib(3)
c = a + b; // c = fib(4)

/* now we have the sequence:
   a  b  c
1, 1, 2, 3
*/
        

The next step gives another sequence number:

          a = b; // now a = fib(3)
b = c; // now b = fib(4)
c = a + b; // c = fib(5)

/* now the sequence is (one more number):
      a  b  c
1, 1, 2, 3, 5
*/
        

…And so on until we get the needed value. That’s much faster than recursion and involves no duplicate computations.

The full code:

function fib(n) {
  let a = 1;
  let b = 1;
  for (let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return b;
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757

The loop starts with i=3, because the first and the second sequence values are hard-coded into variables a=1, b=1.

The approach is called dynamic programming bottom-up.