Unlikely Teacher

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];
    }
}

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.