Getting Down With Fibonacci

Having made the switch from Wordpress to Ghost this week, I decided that I wouldn't bother to migrate my old blog content.

I'm going to make one exception for this post. Partly because I like the title, and partly because I plan to write some similar posts tackling interview style coding problems. This is an interview question that I used to ask first round candidates at Amazon.

How would you write a function that returns the nth term of the Fibonacci sequence.

For an explanation of what the Fibonacci sequence is, check out this wiki. In short, the sequence looks like this:

1, 1, 2, 3, 5, 8, 13, 21, 34..

As you can see, the next number in the sequence is always equal to the sum of the previous two number.

My preferred solution was non-recursive as I think it is more readable (or at least more tangible) and most likely more performant. Avoiding recursion also elimates the risk of creating an infinite loop if it's written incorrectly.

// function accepts the nth term as an argument
function fibonacci(n) {

    // validate argument
    if (!n || typeof(n) !== 'number') { return };

    // create an array and start the sequence
    var seq = [0,1];

    // determine how many iterations are required
    // generate the sequence up to the nth term only
    for (var i = 0; i < (n - 2); i++) {
        // calculate sum of last 2 terms in sequence
        var next = seq[seq.length - 1] + seq[seq.length - 2];
        // add nth term to sequence array
        seq.push(next);
    }

    // retrieve last term in sequence
    var x = seq[seq.length - 1];
    return x;

}

fibonacci(20);  
// returns 4181
// assumes fibonacci sequence is 0 indexed

"Most likely more performant" is a little bit flaky so I benchmarked my solution against the more common recursive solution.

function fibonacci(n) {  
   if (n < 2){
     return n;
   } else {
     return fibonacci(n-2) + fibonacci(n-1);
   }
}

console.log(fibonacci(20));  
// returns 6765
// assumes fibonacci sequence starts [1,1,..]

We'll ignore the debate of whether the sequence starts with a 1 or a 0. My understanding is that modern usage assumes an index of 0.

For the purpose of benchmarking the two, I have changed the starting sequence in my solution to start with one.

var seq = [1,1];  
// instead of
var seq = [0,1];  

As you can see from the test case that I ran on jsperf, the recursive method is 78% slower. 6,788 operations per second compared to 30,438 with my solution.

In conclusion, recursion is cool, it makes you look smart but it's often less performant.

It's also worth noting that if we reguarly needed to retrieve large nth numbers, it would be advisable to run this once, populate a database and retrieve the nth term directly rather than calculating it for every request.

If you're looking to practice these sort of coding problems, take a look at Interview Cake. I keep threatening to have a crack at the weekly problem but never get around to it. Maybe next week...