0

I probably made some stupid mistake, but whenever I try to run this program it always gives me a wrong answer. For example, I ask what is the 5th value of the Fibonacci sequence and it says 7. 

private void jButton1ActionPerformed(java.awt.event.ActionEvent evt) {                                         

     // TODO add your handling code here:
    int n=0;
    try{
        n= Integer.parseInt(jTextField1.getText());    
    }
    catch(NumberFormatException e){
        jTextField2.setText("Please enter valid integers.");
    }
    jTextField2.setText("Fibo value is"+Fibonacci(n));
}  

private int Fibonacci(int n){

    System.out.println(n+"N");
    if (n <=1) {
        return n;
    }
    else{
        return Fibonacci(n-1)+(n-2);        
    }
}
sparkitny
  • 1,503
  • 4
  • 18
  • 23
joshugqa
  • 17
  • 2

2 Answers2

4

Fib is recursively define as Fib(n) = Fib(n-1) + Fib(n-2). Your program defines it as Fib(n) = Fib(n-1) + (n-2)

Answer:

int Fibonacci(int n) {

    System.out.println(n + "N");

    if (n <= 1) {
        return n;
    } else {
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }

}
2

You are trying to find Fibonacci by binary recursion. You should make two recursive calls, like 

return Fibonacci(n - 1) + Fibonacci(n - 2);

but you have made a mistake here -

return Fibonacci(n - 1) + (n - 2);

Your code can be fixed easily by 

int Fibonacci(int n) {
    if (n <= 1)
        return 1;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

The above recursion is called binary recursion since it makes two recursive calls instead of one. Lets calculate the number of calls are needed to compute the kth Fibonacci number :- Let nk denote the number of calls performed in the execution.

n0 = 1
n1 = 1
n2 = n1 + n0 + 1 = 3 > 21
n3 = n2 + n1 + 1 = 5 > 22
n4 = n3 + n2 + 1 = 9 > 23
n5 = n4 + n3 + 1 = 15 > 23 ...
nk > 2k/2

This means that the Fibonacci recursion makes a number of calls that are exponential in k.
In other words, using binary recursion to compute Fibonacci numbers is very inefficient.

This linear recursive version takes O(n) calls.

A more efficient solution :-

int fibonacci(int n) { 
   return fibonacciSlave(0, 1, n);
}

int fibonacciSlave(int a, int b, int n) { 
    if(n <= 1) {
       return b;
    }
   return fibonacciSlave(b, a+b, n-1);
}
vinS
  • 1,417
  • 5
  • 24
  • 37