Fibonacci sequence with memoization still slower than normal recursive solution

Question

I noticed that my recursive Fibonacci algorithm with memoization only works for values greater than 12.

I compared it with someone else's implementation of a method where he also passed an array with it. I thought that passing an array every time, will take too much memory upon re-calling the method thus making the program slower but that was not the case.

I somehow still can't comprehend how my external array is not faster than the normal recursive Fibonacci algorithm. I thought it might be because of the many conditions in my if's that I check that it is slower but I'm not sure.

If possible would you look at my code and tell me what I did wrong or what's going on in the background?

public class Fibonacci2 {
    int memory[];

    public Fibonacci2(int f) {  
        if (memory == null) {
            memory = new int[f+1];

            memory[0] = 0;
            memory[1] = 1;
            memory[2] = 1;
        }   
    }
    
    public int recursive(int f) {
        if (memory[f-1] != 0 && memory[f-2] != 0 && f>2) {
            memory[f] = memory[f-1] + memory[f-2];
        } else if (memory[f-1] == 0 && memory[f-2] != 0 && f>2) {
            memory[f] = recursive(f-1) + memory[f-2];
        } else if (f>2) {
            memory[f] = recursive(f-1) + recursive(f-2);
        }

        return memory[f];
    }
    
}

public class Fibonacci1 {
    public Fibonacci1() {}
    
    public int recursive(int f) {
        if (f > 2) {
            return recursive(f-1) + recursive(f-2);
        } else {
            return 1;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        int fibo = 12;

        Fibonacci1 fiboEx1 = new Fibonacci1();
        Fibonacci2 fiboEx2 = new Fibonacci2(fibo);

        int a = fiboEx1.recursive(fibo);

        long start = System.nanoTime();
        long stop = System.nanoTime();

        System.out.println("fibo of " + fibo + " is " + a);
        System.out.println("Fibonacci time without memorization: " + (stop-start));

        int b = fiboEx2.recursive(fibo);

        start = System.nanoTime();
        stop = System.nanoTime();

        System.out.println("fibo of " + fibo + " is " + b);
        System.out.println("Fibonacci time with memorization: " + (stop-start));
    }
}

Answer 1

I noticed that my recursive Fibonacci algorithm with memorization only works for values bigger than 12.

I’m guessing you mean to write “values smaller than 12”. Either way, this isn’t true: your solution works for values >12, up until the result type overflows.

That said, there are multiple problems with your code.

1. Don’t test for if(memory==null) in your constructor. It’s always true.

2. memory[f-1] != 0 && memory[f-2] != 0 && f>2 — Why are you testing for f > 2 here? The test only makes sense if you test for it at the beginning, to avoid accessing negative array elements. Otherwise the test is redundant.

3. The entire function is more complex than necessary. Separate the logic for accessing the memoised values to make it clearer, simpler and less error-prone:

   public int recursive(int f){
       if (f > 2 && memory[f - 2] == 0) {
           memory[f - 2] = recursive(f - 2);
       }
       if (f > 1 && memory[f - 1] == 0) {
           memory[f - 1] = recursive(f - 1);
       }
       memory[f] = memory[f - 2] + memory[f - 1];
       return memory[f];
   }
   

     … but of course you can and should simplify this even more:

   public int recursive(int f){
       if (memory[f] == 0) {
           memory[f] = recursive(f - 2) + recursive(f - 1);
       }
       return memory[f];
   }
   

   This does the same. But instead of each function call doing multiple redundant checks for memoised values, it simply handles its own value (i.e. f’s), and calls itself for the rest.

4. Fundamentally, having this as a class with a constructor and an additional function makes no sense whatsoever: the function can only be used for getting the Fibonacci number of a single value, which, additionally, needs to be the same in the constructor and the function call (which is error prone!). For example, the following crashes the code: new Fibonacci2(10).recursive(15). So does this: new Fibonacci2(1). Good code wouldn’t allow such errors to happen.

Here’s a solution that doesn’t have these issues:

class Fib {
    static int memory[];

    private static void resizeMemory(int newSize, int[] oldValues) {
        if (newSize < 3) newSize = 3;
        memory = new int[newSize];
        System.arraycopy(oldValues, 0, memory, 0, oldValues.length);
    }

    public static int fib(int n) {
        if (memory == null || memory.length <= n) {
            resizeMemory(n + 1, new int[] {0, 1, 1});
        }

        if (n == 0) return 0;
        if (memory[n] == 0) memory[n] = fib(n - 2) + fib(n - 1);
        return memory[n];
    }
}

But I still wouldn’t actually write a “real” fibonacci implementation like this — maintaining a global memory cache introduces complexity and serves no real purpose. Here’s an efficient implementation that doesn’t use a cache. In practice it will only be less efficient if you calculate a lot of fibonacci numbers, and even then this is unlikely to be the bottleneck.

To illustrate, here’s how this would look like:

private static int fibImpl(int n, int a, int b) {
    if (n == 0) return a;
    if (n == 1) return b;
    return fibImpl(n - 1, b, a + b);
}

public static int fib(int n) {
    return fibImpl(n, 0, 1);
}