# Recursion Optimization: Fibonacci Sequence in Javascript

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.