Can someone explain to me what the recursive Fibonacci code does in Java?

Suppose we enter the number 3.

Since it is neither 0 nor 1, it goes toelse {

Once inside elsewe are sure that the result will be the sum of fibonacci(n-1) + fibonacci(n-2), exemplifying with a diagram it could well be as follows

--------?(3)

------/------\

----?(2)------?(1)

Where we do not know the result "?" but if the number that we are going to enter, the first fibonacci of the diagram of the second line is executed, fibonacci(n-1)which is fibonacci(2), since it is not 0 or 1, it passes to elsewhere it will be executed again fibonacci(n-1) + fibonacci(n-2), the diagram would now be like this

--------?(3)

------/------\

----?(2)------?(1)

--/----\

-?(1)---?(0)

Executing the first fibonacci of the 3rd line, fibonacci(n-1)which is 2 - 1 = 1 fibonacci(1), when executed and being 1, it returns n, which is 1, so we already know what it returnsfibonacci(1)

--------?(3)

------/------\

----?(2)------?(1)

--/----\

-1(1)---?(0)

Executing the second fibonnacci of the third line, fibonacci(n-2)which is 2 - 2 = 0 fibonacci(0), will return 0, since it returns n and n

--------?(3)

------/------\

----?(2)------?(1)

--/----\

-1(1)---0(0)

Now we know that it fibonacci(2)returns fibonacci(1) + fibonacci(0)which is 1 + 0 = 1

--------?(3)

------/------\

----1(2)------?(1)

--/----\

-1(1)---?(0)

We go to the second fibonacci of the second line that we know fibonacci(1)= 1, so.

--------?(3)

------/------\

----1(2)------1(1)

--/----\

-1(1)---0(0)

Again we know that it fibonacci(3)returns fibonacci(2) + fibonacci(1)which is 1 + 1 =

--------23)

------/------\

----1(2)------1(1)

--/----\

-1(1)---0(0)

But as they said, the best thing would be to debug or with simple prints it can help you

To understand the algorithm, we can start with the base cases and work our way up:

fibonacci(0) --> 0
fibonacci(1) --> 1

For fibonacci(2)we have to apply the part of else:

fibonacci(2) --> fibonacci(1) + fibonacci(0)

To calculate the sum, it is necessary to know the result of the two calls that, in the case of addition, are evaluated from left to right. Therefore we have the following sequence:

fibonacci(2)
--> fibonacci(1) + fibonacci(0)
--> 1 + fibonacci(0)
--> 1 + 0
--> 1

For fibonacci(3):

fibonacci(3)
--> fibonacci(2) + fibonacci(1)
--> (fibonacci(1) + fibonacci(0)) + fibonacci(1)
--> (1 + fibonacci(0)) + fibonacci(1)
--> (1 + 0) + fibonacci(1)
--> 1 + fibonacci(1)
--> 1 + 1
--> 2

In this last case you can see that it fibonacci(1)is invoked twice. The larger the integer, the more times the calculations will be repeated. (An optimization way would be to save the result for later calculations ( "memoization" )).

The process is fairly linear, first one function and then the other. There is no mixing of stacks since the functions are not called simultaneously.

Doing an exercise of imagination, to calculate fibonacci(n)you don't need more than nrecursion levels, which is the same, no more than n "stackframes" .

To see the trace yourself you could use the java debugger or if you can't show what you're doing in the console:

public int fibonacci(int n) {

  if ((n == 0) || (n == 1)) // base cases
       System.out.println("Devuelvo +"n)
       return n;
    else
       System.out.println("Entro en el else con +"n)      
        // recursion step
      return fibonacci(n - 1) + fibonacci(n - 2);
}

Although you can use other methods for the fibonacci series

public class fibonacci
{
public static void main (String[] args)
{
int a=0,b=1,c,hasta,i;
cantidad=15; //indica la cantidad de numeros en la serie fibonacci


for(i=0;i<hasta;i++)
{
c=a+b;
a=b;
b=c;
System.out.print(" "+a);
}
}

}