I have the following question: How do I implement the Fibonacci sequence recursively for a number that I pass to it as a parameter?
I have the following for, which calculates the fibonacci sequence for the first 10 numbers:
int i = 0, a = 0, b = 1, c = 0;
System.out.println(" ");
System.out.println("Fibonacci con estructura for: ");
for (i = 0; i < 10; i++) {
if (i < 9) {
System.out.print(a + ",");
c = a + b;
a = b;
b = c;
} else {
System.out.println(a);
}
}
My question is how I could do this sequence recursively and in addition to the number that the user passes through the keyboard. I have the following at the moment:
public class recursivo {
public static void main(String[]args) {
int n;
Scanner teclado = new Scanner(System.in);
System.out.println("Calcular fibonacci");
System.out.println("Introduce el numero del que deseas hacer fibonacci");
n = teclado.nextInt();
}
public static int Fibonacci(int sol, int n) {
if (n == 1 || n==2) {
sol = 1;
} else {
}
return sol;
}
}
Thank you very much in advance, greetings.
Your first algorithm uses the dynamic programming technique, which is much more efficient in execution time than the recursive programming technique, which has a much slower execution time and in this specific case it has several drawbacks since if we use this recursive technique, a call tree will be created that will have functions with the same parameters n-times, or in other words, the same thing is calculated several times, an example suppose that we are going to calculate the fibbonacci function for n = 5; recursively it would be the sum of all fibbonacci that precede fib(5) something like F = fib(5) + fib(4) + fib(3) + fib(2) + fib(1) + fib(0), if we apply the function F = fib(n-1) + fib(n-2), and we go through the call to the first function fib(before the operator +)
F(5) = fib(4) + fib(3) to the right branch of the function we would be calculating fibbonnaccis that we have previously calculated which is inefficient, after all this explanation I recommend that you use the dynamic programming technique and that you look for more information on the internet about this.
Recursively it is done like this, which is actually what you are asking