Home Fibonacci Recursion Not working
Reply: 2

Fibonacci Recursion Not working

joshugqa
1#
joshugqa Published in 2018-01-13 03:40:10Z

This question already has an answer here:

  • Java recursive Fibonacci sequence 30 answers

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);        
    }
}
Huy Vo
2#
Huy Vo Reply to 2018-01-13 03:44:09Z

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);
    }

}
vinS
3#
vinS Reply to 2018-01-13 04:19:24Z

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);
}
You need to login account before you can post.

About| Privacy statement| Terms of Service| Advertising| Contact us| Help| Sitemap|
Processed in 0.312643 second(s) , Gzip On .

© 2016 Powered by mzan.com design MATCHINFO