Code Kata: the Fibonacci sequence

The Fibonacci sequence (named after the Italian mathematician Leonardo Fibonacci) is a sequence of numbers where each number is the sum of the previous two numbers. This lends itself quite well to a recursive approach:


 int fibonacci(int term){
       if (term==0) return 0;
       if (term==1) return 1;
       return fibonacci(term - 1) + fibonacci(term - 2);
   }

pros: clean, concise code, very easy to read.

cons: totally useless for anything else than a very small sequence. The dual recursive calls on the last line are performance killers eg. it takes several thousand calls just to calculate fibonacci(20).

A better (as in faster) solution:

  int fibonacci(int f1, int f2, int term){
        if (term==0) return 0;
        if (term==1) return 1;
        if ( term-->2)
            return fib2(f1 + f2, f1, term);
        else
            return f1+f2;
    }

pros: much quicker. computes fibonacci(2000) in under 400 microseconds on an intel core I5.

cons: calculating a sequence with a term greater than 10,000 is pretty much guaranteed to trigger a stack overflow error. This is because in the absence of tail call optimization each recursive method call involves allocating a new stack frame, finally exceeding the jvm stack size.

This leads to a third implementation where the logic is changed to “flatten” the recursive calls into a while loop like so:

    static int fibonacci(int f1, int f2, int term){
        if (term==0) return 0;
        if (term==1) return 1;
        while (term-->2) {
            int tmp = f1;
            f1 = f1  +f2;
            f2 = tmp;
        }
        return f1;
    }

The code doesn’t quite flow as nicely as the first recursive implementation – but more importantly – it wont trigger a stack overflow and it’s significantly faster than any of the two recursive functions eg. fibonacci(2000) is calculated within around 100 micros.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s