Interview Coding: Fibonacci function

Writing a function that returns the nth number in a Fibonacci sequence can either be the easiest interview whiteboard question or the hardest.  If you're like me, your daily activities revolve around events, delegates, background threads, data grid views, custom controls, or reading about some new area of C# and .NET that you've never encountered before.  A strange sequence of numbers stuns you like a phaser on Star Trek.  Even worse, you've probably heard of Fibonacci during your days at the University or in other interviews, but you just can't recall what it is.

If you're unfamiliar with Fibonacci, the interviewer will usually prep you by giving you a list of the first few numbers:

0 1 1 2 3 5 8 13 21

The interviewer should explain the most obvious property of the Fibonacci sequence: each number is the sum of the previous two numbers, if N > 1.  1 is the sum of 0+1, 2 is the sum of 1+1, 3 is the sum of 2+1, etc.  There are other properties of the Fibonacci sequence, which you can read about on this Wikipedia article.

You will be asked to write a function that returns the result of Fib(n).  The Wikipedia article explains clearly, if N > 1, the Fibonacci result is F(n-1) + F(n-2).  If you see this, you can almost write the code, but it may not be explained to you in this fashion.  The interviewer may tell you that Fib(1) == 1, and Fib(5) == 5.  How can that be?  It's helpful to think of the Fibonacci sequence in an array, starting at index 0:

Now you can see, ironically enough, that Fib(5) is 5, but there's a logical reason, it's at index 5.  Fib(4) doesn't equal 4, it equals 3, because it is the 4th (after 0) in the sequence.  Once you understand that, you can start to write the code:

int fib(int n)
{
    if (n <= 1)
        return n;

    return fib(n-1) + fib(n-2);

}

This is the preferred way to write a Fibonacci function, because it uses recursion.  If N is 0 or 1, that value will be returned.  If N is greater than 1, the fib function calls itself recursively, not once, but twice, with the 2 previous numbers in the sequence, n-1 and n-2.  If you call this with N set to 2, then fib will call itself twice with fib(1) and fib(0), which will return 1 and 0, and the sum will be 1.  It works like this for any higher value as well.

The wrong approach would be to set the Fibonacci sequence in a pre-defined array, and going to the Nth index and returning the value there.  But the interviewer will point out that the sequence can go on infinitely and you could never set down all the values.

This is not a perfect function.  If the numbers are negative, a negative value is returned.  You can argue that there will be a buildup of recursive stack values (if N is 10000 the stack will be enormous), or that we are losing performance by making two recursive calls in one function.

Why is recursion the preferred method?  It makes the code simple and easy to understand.  If you look at the Fibonacci definition in the Wikipedia article, the code above resembles that pseudocode definition almost perfectly.  You've solved the problem in the fewest lines of code.  We always hope to hire programmers who can deliver elegant solutions to complex problems.