Why is this js code so slow?

Question

This code takes 3 seconds on Chrome and 6s on Firefox. If I write the code in Java and run it under Java 7.0 it takes only 10ms. Chrome's JS engine is usually very fast. Why is it so slow here? btw. this code is just for testing. I know it's not very practical way to write a fibonacci function

fib = function(n) {
  if (n < 2) {
    return n;
  } else {
    return fib(n - 1) + fib(n - 2);
  }
};

console.log(fib(32));

Answer 1

This isn't fault of javascript, but your algorithm. You're recomputing same subproblems over and over again, and it gets worse when N is bigger. This is call graph for a single call:

                  F(32)
               /         \
            F(31)            F(30)
          /     \           /      \
      F(30)     F(29)     F(29)    F(28)
    /  \      /     \     /   \     |    \
F(29) F(28) F(28) F(27) F(28) F(27) F(27) F(26)

... deeper and deeper

As you can see from this tree, you're computing some fibonacci numbers several times, for example F(28) is computed 4 times. From the "Algorithm Design Manual" book:

How much time does this algorithm take to compute F(n)? Since F(n+1) /F(n) ≈ φ = (1 + sqrt(5))/2 ≈ 1.61803, this means that F(n) > 1.6^n . Since our recursion tree has only 0 and 1 as leaves, summing up to such a large number means we must have at least 1.6^n leaves or procedure calls! This humble little program takes exponential time to run!

You have to use memoization or build solution bottom up (i.e. small subproblems first).

This solution uses memoization (thus, we're computing each Fibonacci number only once):

var cache = {};
function fib(n) {
  if (!cache[n]) {
    cache[n] = (n < 2) ? n : fib(n - 1) + fib(n - 2);
  }
  return cache[n];
}

This one solves it bottom up:

function fib(n) {
  if (n < 2) return n;
  var a = 0, b = 1;
  while (--n) {
    var t = a + b;
    a = b;
    b = t;
  }
  return b;
}

Answer 2

As is fairly well known, the implementation of the fibonacci function you gave in your question requires a lot of steps if implemented naively. In particular, it takes 7,049,155 calls.

However, these kinds of algorithms can be greatly sped up with a technique known as memoization. If you see the function call fib(32) taking several seconds, the function is being implemented naively. If it returns instantly, there is a high probability that the implementation is using memoization.