Fibonacci Code Golf

The other day, one of my colleagues said he'd once been asked to code a function to produce the nth fibonacci number for a job interview.  We got talking about the shortest possible function to do this.

A fibonacci number is the sum of the two previous fibonacci numbers.  The first and second fibonacci numbers are defined to be 1.  That makes the third 2 (1 + 1), the fourth, 3 (2 + 1) and the fifth, 5 (3 + 2).  Cake.

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

Beautiful, Recursive and Horribly Inefficient

A clean and simple implementation in C might look like this:

int fibonacci(int n)
{
    if (n == 0) 
        return 0;
    else if (n == 1 || n == 2) 
        return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Since I'm not a golfer, and code golf and mini golf are the only kinds of golf I play, I came up with the following in (bad) C.

f(n){return n<3?1:f(n-1)+f(n-2);}

Now, this one isn't correct for 0, which should return 0, so let's revise it at the expense of four more characters.

f(n){return n<3?n?1:0:f(n-1)+f(n-2);}

That works.  Kind of.  The highest n you can pass it is 46 (returning 1,836,311,903), because after that it overflows the 32 bit signed int (which holds a maximum value of 2³¹-1 = 2,147,483,647).

Okay, but the real problem with these functions is how phenomenally slow they are.  You wouldn't be able to get much past 46 anyway without rendering your machine absolutely useless.  This is a classic recursive function, that is, a function that calls itself.  This fibonacci function itself is often used to demonstrate the elegance of many functional languages.  For example, here it is in OCaml:

let rec fib = function
  | 0 -> 0
  | 1 -> 1
  | n -> fib (n-1) + fib (n-2)

As it turns out, to calculate f(46), you end up calling f() 3,672,623,805 times!  f(47) makes 5.9 billion and f(50) makes nearly 20 billion calls.  The recursive fibonacci sequence grows in number of calls on the order of 2ⁿ, which makes it roughly equivalent to the rice and chessboard puzzle.

Ugly Lookup Table

So we need to rework it and make the shortest version that isn't super inefficient.  Since 46 in the maximum n that fits in a signed 32-bit int (and 47 unsigned), we could just make a precomputed look-up table.

int fib(int n)
{
    static int fibs[] =
      { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 
        610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 
        46368, 75025, 121393, 196418, 317811, 514229, 832040, 
        1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 
        24157817, 39088169, 63245986, 102334155, 165580141, 
        267914296, 433494437, 701408733, 1134903170, 1836311903 };
    return fibs[n];
}

That's as fast as you're probably going to get, but it's ugly and not particularly short.

Iterative and Fast

You can also do it iteratively, without any recursion at all:

int fib(int n)
{
    if (!n) return 0;
    int p = 0, q = 1;
    for (int i = 2; i < n; i++)
      { int t = p; p = q; q = t + p; }
    return p + q;
}

It's starting to get a little longer, though, so I don't bother to shove it on one line or abbreviate int fib(int n) into f(n) like with the shortest ones above.  This function can be literally billions of times faster that the first ones.

Returning to Recursion, with Memoization

But..  I've got a short recursive version that outperforms this one on the whole, especially when called more than once, because it builds up a look-up table dynamically, with a simple technique broadly called memoization.

f(n){static int m[64]={0,1,1,0};return !n||m[n]?m[n]:(m[n]=f(n-1)+f(n-2));}

Fast and short.

No Recursion, No Iteration, Just a Formula

Let's do one more.

There is a closed form calculation of the fibonacci number that requires neither iteration nor recursion.  You just calculate it and there you go.  Here is my shortest implementation of that:

f(n){double A=sqrt(5),B=A/2;return(pow(0.5+B,n)-pow(0.5-B,n))/A;}

Short.  No iteration, no recursion.  Over several calls, I figure this will be slower than the previous function, but it's way slicker.