How to make a negative Fibonacci sequence in Java using recursion?

Question

I have to write a program that returns Fibonacci number, but not only positive. I don't know what is not right in the way I've wrote it, but my code works with positive numbers and not with negative ones.

public static int negFib(int n) {
    if(n==0 || n==1) {
        return n;
    }
    if(n==-1) {
        return 1;
    }
    if(n<0 && n%2==0) {
        //return negFib(n+2) - negFib(n+1);
        return (-1<<(n+1))*(negFib(n-1) + negFib(n-2); // Fibonacci negative
        //F(n)=F(n+2)−F(n+1)
        //F(−1)=F(1)−F(0)=1−0=1 , F(−2)=F(0)−F(1)=0−1=−1
    } 
    return negFib(n-1) + negFib(n-2); //Fibonacci positive      
}

Answer 1

Well, if you want to use the F_−n = (−1)ⁿ⁺¹F_n formula:

public static int negFib(int n) {
    if(n==0 || n==1) {
        return n;
    }
    if(n==-1) {
        return 1;
    }
    if(n<0) {
        int sign = n % 2 == 0 ? -1 : 1;
        return sign * negFib(-n);
    } else {
        return negFib(n-1) + negFib(n-2);
    }     
}

Your attempt had several issues:

• for negative n (either odd or even), you should make the recursive call for -n-1 and -n-2.
• your calculation of the sign - (-1<<(n+1)) - is wrong.