CODEWITHSUNDEEP
javarecursionfibonaccimemoization
Alex
Alex

Reputation: 63

Making this recursive fibonacci with memoization even faster?

Is there a way to make this program run faster? It is already faster than a HashMap version I tried making, but it's still too slow around the 45 mark, according to where I'm submitting it to. Is there any modification I could do to improve it? 

import java.util.Scanner;

public class Fibo {
    static long[] cache;
    static long ans;

    public static long fibo(int n) {
        if (n == 0) 
            return 1;
        if (n < 2) 
            ans = 1;
        else
            ans = fibo(n - 1) + fibo(n - 2);
        cache[n - 1] = ans;
        return ans;

    }

    public static void main(String[] args) {
            Scanner input = new Scanner(System.in);
            System.out.println("test");
            int num = input.nextInt();
            input.close();
            cache = new long[num];
            long ans = fibo(num);
            System.out.println(ans);
    }
}

Upvotes: 1

Views: 1081

Answers (2)

Bohemian
Bohemian

Reputation: 425003

You could make it faster by actually using the cached values:

public static long fibo(int n) {
    if (cache[n] > 0) {
        return cache[n];
    }
    ...
    cache[n] = ans; // you are saving at the wrong index
    ...
}

Although using memoization is "fast" at O(n), there's a mathy O(log n) solution that super fast.

Upvotes: 2

rgettman
rgettman

Reputation: 178263

You are attempting to memoize answers in your cache, but you aren't utilizing it. Check your cache before any other calculations. Also, you'll get an ArrayIndexOutOfBoundsException when you get to fibo(0) because you're subtracting one. Remove the subtraction and increase the size of your array to account for it.

public static long fibo(int n) {
    // Try cache first.
    if (cache[n] != 0) return cache[n];
    if (n == 0) 
        return 1;
    if (n < 2) 
        ans = 1;
    else
        ans = fibo(n - 1) + fibo(n - 2);
    // Don't subtract one.
    cache[n] = ans;
    return ans;
}

In main, make room for the answer to fibo(num).

cache = new long[num + 1];

Upvotes: 3

Related Questions