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.