The Fibonacci Sequence: 1, 1, 2, 3, 5, 8, 13, 21, …

The nth Fibonacci number is defined as (n-1) + (n-2). For example, the 5th Fibonacci number is the sum of the 4th (n-1) and 3rd (n-2) Fibonacci numbers: 3 + 2 = 5.

The 8th Fibonacci number is the sum of the 7th (8-1) and 6th (8-2) Fibonacci numbers: 13 + 8 = 21.

A recursive Fibonacci function in Javascript works as follows:

var recursiveFib = function(n) {
  // base case: the first two Fib numbers are 1
  if (n <= 2) { 
    return 1; 
  } else {
    // The nth Fib # is (n-1) + (n-2)
    return recursiveFib(n-1) + recursiveFib(n-2);
  }
}

This works, but my browser cannot compute recursiveFib(100); Too much for it to handle?

We can optimize this function using tail-recursion. In the recursiveFib function, a call stack is created to keep track of all the calls to recursiveFib.

function tailRecFib(n) {
  return function(n,a,b) {
    return n > 1 ? arguments.callee(n-1,b,a+b) : a;
  }(n,1,1);
}

This tail-recursive version is more efficient because it simply accumulates the Fibonacci computation in an argument to the function (a+b). No longer do we need to store a tremendous amount of calculations on the stack – it’s now treated much like an iterative for loop.

Finally, there exists a closed-form formula to calculate the nth Fibonacci number. Using this formula, we can arrive at the function:

function closedFormFib(n) {
  var sqrt5 = Math.sqrt(5);
  var a = (1 + sqrt5)/2;
  var b = (1 - sqrt5)/2;
  var ans = Math.round((Math.pow(a, n) - Math.pow(b, n))/sqrt5);
  return ans;
}

* These functions do contain rounding errors due to Javasript’s internal handling of numbers.