Fibonacci

Calculating the n-th Fibonacci in different ways:

// Recursive
function fib(n){
  if (n < 2) return n;
  return fib(n-1) + fib(n-2);
}

// Memoized
function memFib(n){
  return memFib[n] || (memFib[n] = fib(n));
}

// Mathematical
function mathFib(n){
  return Math.floor(Math.pow(Phi, n)/Math.sqrt(5) +.5);
}

How do they compare in speed?

[fib, memFib, mathFib].map(function(fn){
  var t0 = +new Date
  fn(30);
  return +new Date - t0
});

Don't get your panties in a bunch just yet. This is an unfair fight:

1. fib is simply horrible, performance-wise. It's the easiest to understand and best for demonstrating recursive functions, but that's it.
   
   
2. memFib is a great example for memoization, as it executes almost linearly, except for those numbers which have not been used yet. If you try running memFib with n=40, you will start feeling the pain, but only the first time.
   
   An important point to make here about memoization is, if your function will be called many times and always returns the same result given the same arguments, memoizing is your friend.
   
   

We will approach browser recursion limits quickly, so I will add two more contenders:

// Y-combinator
var Yfib = Y(function(fn){ return (function(n){
  if (n < 2) return n;
  return fn(n-1) + fn(n-2);
}); });

// Memoized Y-combinator
var YmemFib = Ymem(function(fn){ return (function(n){
  if (n < 2) return n;
  return fn(n-1) + fn(n-2);
}); });

This is a whole different game, with n=1000:

[mathFib, YmemFib].map(function(fn){
  var t0 = +new Date
  fn(1000);
  return +new Date - t0
});

Firefox 3.6.10 cries somewhere between n=1000 and n=2000 about too much recursion, and the difference is less than 10 milliseconds in favor of the mathematical formula.
Chrome 6.0.472.63 can handle at least n=6000 before exhausting its stack and has a difference of about 2 milliseconds. BOOM.

The Much Anticipated Morale Of The Leonardo Of Pisa Thingamajigs

1. Go for the mathematical solution first. If you are not smart enough, ask Google. If Google is not smart enough, ask Tyler. Seriously.
   
   
2. Memoize. Remember this. Get it?
   
   
3. Use a Y-combinator. You don't have to understand how to use it, and good luck trying. Seriously. Here you go:

   function Y(fn) {
     return function(x) {
       return (fn(function(n){
        return (Y(fn))(n);
       }))(x);
     };
   }
   

   To help you understand, try: matt.might.net, fixed point combinator on Wikipedia, Electronics and Computing Systems at the University of Cincinnati, the book To Mock a Mockingbird, and/or some entheogens.
   
   

The short answer: wrap this equivalent of bacon around everything.

/**
 * Memoizing Y-combinator (aka triptonomikon).
 */
function Ymem(fn) {
  var mem = this;
  return function(x) {
    return mem[x] || (mem[x] = (fn(function(n){
     return (Ymem.call(mem, fn))(n);
    }))(x));
  };
}

This should keep you busy until the next post.