How to make fibonacci method? [closed]

The Fibonacci sequence reads:

1 1 2 3 5 8 13 21 ...

The base-case is simply wrong:

@Cacheable
public static int f(int n) {
    if (n <= 2) {//base case
        return 1;  //first two numbers are 1
    } else {
        return f(n - 1) + f(n - 2);
    }
}

This gives for 4: 3.

Note: these are not “array indices”, but “human indices”.

But this method is actually way too inefficient to be pratical. You should use dynamic programming or an iterative variant to calculate this.

@Cacheable is a spring-directive that turns a function into a function with memory. In other words, once f(4) is calculated, it will not recalculate it, but get it from a store. Removing @Cacheable will still give the correct result, but will take way too much time for a large n.

This thus turns the algorithm in an efficient dynamic programming approach.

An iterative algorithm is thus:

public static int f(int n){
    if (n <= 2) {//base case
        return 1;  //first two numbers are 1
    } else {
        int a = 1;
        int b = 1;
        for(int i = 2; i < n; i++) {
            int t = a+b;
            a = b;
            b = t;
        }
        return b;
    }
}

Since this runs in linear time whereas the previous one takes exponential time.

jdoodle.

Or as @Jarlax says, you can also compute this in O(log n) time using this approach.