Let’s consider the snippet of code you put in the question, just assigning the return of the call to a variable, to simplify the explanation:
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
resultado = fibonacci(5)
The memory on the computer has an address and a value. For didactic purposes, let’s assume that this memory is sequential, starting at the 0x01 address and that it has a label, referring to the variable name:
The program will execute the last line of the code, reserving a space in memory for the variable and set the return of the function as its value:
resultado = fibonacci(5)
In memory stays:
Step 1
To know what value fibonacci(5)
, the function fibonacci
is executed:
- The function
fibonacci
is called with parameter n = 5
;
- It appears that
n
is less than or equal to 1. False, executes the else
;
- Return the value of
fibonacci(4) + fibonacci(3)
;
That is, the value of fibonacci(5)
will be fibonacci(4) + fibonacci(3)
. Then in memory, it would be:
Step 2
Then, the program will first try to calculate the value of fibonacci(4)
, because the expression is analyzed from left to right:
- The function
fibonacci
is called with parameter n = 4
;
- It appears that
n
is less than or equal to 1. False, executes the else
;
- Return the value of
fibonacci(3) + fibonacci(2)
;
That is, the value of fibonacci(4)
will be fibonacci(3) + fibonacci(2)
. Then in memory, it would be:
Step 3
So, to know the value of fibonacci(4)
, the program needs to know the value of fibonacci(3)
and fibonacci(2)
. Analyzing from left to right, first is calculated fibonacci(3)
:
- The function
fibonacci
is called with parameter n = 3
;
- It appears that
n
is less than or equal to 1. False, executes the else
;
- Return the value of
fibonacci(2) + fibonacci(1)
;
That is, the value of fibonacci(3)
will be fibonacci(2) + fibonacci(1)
. Then in memory, it would be:
Step 4
The same logic: to know the value of fibonacci(3)
, before it is necessary to know the value of fibonacci(2)
and fibonacci(1)
. From left to right, calculate the value of fibonacci(2)
:
- The function
fibonacci
is called with parameter n = 2
;
- It appears that
n
is less than or equal to 1. False, executes the else
;
- Return the value of
fibonacci(1) + fibonacci(0)
;
That is, the value of fibonacci(2)
will be fibonacci(1) + fibonacci(0)
. Then in memory, it would be:
Step 5
To calculate the value of fibonacci(2)
then you need to fibonacci(1)
and fibonacci(0)
. From left to right, calculate first fibonacci(1)
:
- The function
fibonacci
is called with parameter n = 1
;
- It appears that
n
is less than or equal to 1. True;
- Return the value of
n
(1);
At this point, the refusal is interrupted briefly, because the value no longer depends on another function call. Thus, in memory it is:
Step 6
Thus, having the value of fibonacci(1)
, this is replaced by fibonacci(2)
:
Step 7
But it is still necessary to calculate the value of fibonacci(0)
:
- The function
fibonacci
is called with parameter n = 0
;
- It appears that
n
is less than or equal to 1. True;
- Return the value of
n
(0);
So in memory it is:
Step 8
This value is promptly replaced in the value of fibonacci(2)
:
Step 9
The value of fibonacci(2)
is obtained by summing 1+0 = 1 and is replaced by fibonacci(3)
:
Step 10
To calculate the final value of fibonacci(3)
the value of fibonacci(1)
again, then the call is made again:
- The function
fibonacci
is called with parameter n = 1
;
- It appears that
n
is less than or equal to 1. True;
- Return the value of
n
(1);
Staying in memory:
Step 11
This value is promptly replaced in fibonacci(3)
, getting:
Step 12
The value of fibonacci(3)
then it will be worth 1+1 = 2, being replaced in fibonacci(4)
:
Step 13
But again it takes the value of fibonacci(2)
, then:
- The function
fibonacci
is called with parameter n = 2
;
- It appears that
n
is less than or equal to 1. False, executes the else
;
- Return the value of
fibonacci(1) + fibonacci(0)
;
Staying in memory:
Step 14
We already know that fibonacci(1)
will return 1 and fibonacci(0)
will return 0, so to simplify, I will directly put your values in fibonacci(2)
:
Step 15
Leaving the value of fibonacci(2)
equal to 1+0 = 1, being promptly replaced in fibonacci(4)
:
Step 16
Thus the value of fibonacci(4)
is equal to 2+1 = 3 and is promptly replaced in fibonacci(5)
:
Step 17
To further calculate the final value of fibonacci(5)
the value of fibonacci(3)
:
- The function
fibonacci
is called with parameter n = 3
;
- It appears that
n
is less than or equal to 1. False, executes the else
;
- Return the value of
fibonacci(2) + fibonacci(1)
;
That is, the value of fibonacci(3)
will be fibonacci(2) + fibonacci(1)
:
Step 18
The value of fibonacci(2)
:
- The function
fibonacci
is called with parameter n = 2
;
- It appears that
n
is less than or equal to 1. False, executes the else
;
- Return the value of
fibonacci(1) + fibonacci(0)
;
Staying in memory:
Step 19
As we already know, fibonacci(1)
is worth 1 and fibonacci(0)
is worth 0, then replacing the values:
Step 20
Resulting in fibonacci(2)
equal to 1+0 = 1, being promptly replaced in fibonacci(3)
:
Step 21
The value of fibonacci(1)
, that we already know is worth 1:
Step 22
Thus the value of fibonacci(3)
will be 1+1 = 2 and is promptly replaced in fibonacci(5)
:
Step 23
Finally, the value of fibonacci(5)
will be valid 3+2 = 5, being replaced promptly in resultado
:
Therefore, when executed:
resultado = fibonacci(5)
The value of resultado
will be 5. This value can be proved by executing the code.
See working on Ideone.
Recursion works the same, regardless of the situation. You’ve already opened this question asking about how recursion works, so I think it will be better if you [Dit] the question and put EXACTLY what is your difficulty. What don’t you understand? My Javascript response didn’t help you at all?
– Woss
You don’t understand recursion or Fibonacci?
– Math
You know how to test your table?
– Woss
So guys, what I don’t understand is how codes work in recursion, the javascript code didn’t help me 100%, it cleared up a little bit how recursion works, but it didn’t clear up my doubts.
– Eduardo
@Eduardo if the answer cleared your doubt, you can accept it by pressing the icon ✓ on the left side of it.
– Woss