Home Fibonacci Recursion Not working

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