If you were given a task to compute the nth **Fibonacci number**, how would you do it?

You would go straight away and write a recursive function right?

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

elapsed for n=30: 31 ms

elapsed for n=40: 3016 ms

*Well think again*. Because there might be a better way of doing it.

public static int getNumberLoop(int n) {

if (n == 0 | n == 1) {

return 1;

} else {

int[] fib = new int[n + 1];

fib[0] = 1;

fib[1] = 1;

for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
}
[/sourcecode]
elapsed for n=100000: 31 ms
If we compare the elapsed time (in ms) between the two functions, we can clearly see which one is better.
Anyway, I've found an invaluable book called **Algorithms** from where I got the example above.

I know a lot of programmers (myself included) who are easily satisfied with a workable solution rather than an efficient one.

I hope someday (with enough time and practice) I can be an expert on this topic too.

## Leave a Reply