Fibonacci Sequence using Cache

Question

I am trying to make use of a cache to improve the performance of my Fibonacci method. However, it is still taking a lot of time to compute even fibonacci(40).

import java.util.Scanner;
public class FibWithCache {

    public static void main(String args[]) {
        System.out.println("Enter Fibonacci index: ");
        Scanner sc = new Scanner(System.in);
        int index = sc.nextInt();
        sc.close();

        System.out.println(fibonacci(index));
    }

    private static long fibonacci(int index) {

        long result = 0;
        long[] fibCache = new long[200];

        if(index==0)
            return 0;
        else if(index == 1)
            return 1;
        else if(fibCache[index] != 0)
            return fibCache[index];
        else {
            result = fibonacci(index-1) + fibonacci(index-2);
            fibCache[index] = result;
            return result;
        }
    }
}

Why am I unable to benefit from the cache?

NPE · Accepted Answer · 2017-09-06 11:14:18Z

12

Hint: The issue is that each recursive call to fibonacci() has its own cache. For every call you create an empty cache, store something in it, and immediately discard it.

What you want is one cache shared by all the calls.

I'll let you figure out how best to do it. :)

answered Sep 6, 2017 at 11:14

NPE

503k114 gold badges970 silver badges1k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Abhishek Over a year ago

I declared the array in the class and it worked. Thanks a lot

ifma · Accepted Answer · 2017-09-06 11:15:31Z

3

There should only be one instance to fibCache (it has to be static).

answered Sep 6, 2017 at 11:15

ifma

3,8584 gold badges30 silver badges40 bronze badges

Comments

Tomerikoo · Accepted Answer · 2021-11-02 07:59:53Z

1

public class FibonacciCache {

    private int[] cache = new int[1000];
    
    public FibonacciCache(){
        // n de 1 = 1;
        cache[1] = 1;
    }

    public int fibonacciDe(int n){
        if(cache[n] != 0){
            return cache[n];
        }
    
        // n de 0 = 0
        if(n <= 0){
            return 0;
        }
                        
        int result = fibonacciDe(n-1) + fibonacciDe(n-2);
        cache[n] = result;
        return result;
    }

edited Nov 2, 2021 at 7:59

Tomerikoo

19.6k16 gold badges57 silver badges68 bronze badges

answered Nov 2, 2021 at 7:44

Himanshu Kumar

291 bronze badge

1 Comment

Elikill58 Over a year ago

Can you edit your answer to explain why and how this code can reply to the question ?

Collectives™ on Stack Overflow

Fibonacci Sequence using Cache

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related