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.

### Like this:

Like Loading...

*Related*