Calculating Fibonacci numbers

The following problem is currently taking more than 8 seconds to execute. Please help me to modify the program, so that execution time will be reduced.

var yourself = {
fibonacci : function(n) {
    if (n === 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }
    else {
        return this.fibonacci(n - 1) +
            this.fibonacci(n - 2);
    }
}
};

This is one of the standard examples for algorithmic complexity. This algorithm is very easy to understand since it matches the mathematical definition well, but performs miserably since it's trying to calculate a number that grows exponentially by adding 0s and 1s together.

The key observation is that to calculate, say, fibonacci(5), it has to recursively calculate fibonacci(4) and fibonacci(3). Then to calculate fibonacci(4), it has to calculate fibonacci(3) again, which is completely wasteful. There are several things we can do to go faster:

• Build from the bottom up. Start two variables a=0 and b=1, then run a loop where you set a=b and b=a+b (careful to not blast values as you're using them). This is how you would do it by hand.

• Use your recursive solution, but cache the results so that it doesn't repeat work. This is called memoization.

• Use the closed-form formula.

StackExchange Code Review Q#109680, answer score: 10