Determine the nth Fibonacci term with recursion

Let's consider the snippet of code you put in the question, just assigning the callback 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 address 0x01 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 setting the return of the function to be its value:

resultado = fibonacci(5)

In memory is:

Step 1

To know which value of fibonacci(5), the function fibonacci is executed:

1. the function fibonacci is called with parameter n = 5;
2. check if n is less than or equal to 1. False, execute o else;
3. return the value of fibonacci(4) + fibonacci(3);

That is, the value of fibonacci(5) will be fibonacci(4) + fibonacci(3). So in memory, it would be:

Step 2

Then the program will first try to calculate the value of fibonacci(4), as the expression is parsed from left to right:

1. the function fibonacci is called with parameter n = 4;
2. check if n is less than or equal to 1. False, execute o else;
3. return the value of fibonacci(3) + fibonacci(2);

That is, the value of fibonacci(4) will be fibonacci(3) + fibonacci(2). So 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). Parsing from left to right, first is calculated fibonacci(3):

1. the function fibonacci is called with parameter n = 3;
2. check if n is less than or equal to 1. False, execute o else;
3. return the value of fibonacci(2) + fibonacci(1);

That is, the value from fibonacci(3) will be fibonacci(2) + fibonacci(1). So in memory, it would be:

Step 4

The same logic: to know the value of fibonacci(3), first you need to know the value of fibonacci(2) and fibonacci(1). From left to right, the value of fibonacci(2) is calculated:

1. the function fibonacci is called with parameter n = 2;
2. check if n is less than or equal to 1. False, execute o else;
3. return the value of fibonacci(1) + fibonacci(0);

Or that is, the value of fibonacci(2) will be fibonacci(1) + fibonacci(0). So in memory, it would be:

Step 5

To calculate the value of fibonacci(2) then you need fibonacci(1) and fibonacci(0). From left to right, first calculate fibonacci(1):

1. the function fibonacci is called with parameter n = 1;
2. check if n is less than or equal to 1. True;
3. return the value of n (1);

At this point, the recusiveness is interrupted briefly, as the value no longer depends on another function call. Thus, in the memory 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):

1. the function fibonacci is called with parameter n = 0;
2. check if n is less than or equal to 1. True;
3. return the value of n (0);

Then in memory is:

Step 8

This value is readily substituted to the value of fibonacci(2):

Step 9

The value of fibonacci(2) is obtained by adding 1+0 = 1 and is replaced by fibonacci(3):

Step 10

To calculate the final value of fibonacci(3) is I need the value of fibonacci(1) again, then the call is made again:

1. the function fibonacci is called with parameter n = 1;
2. check if n is less than or equal to 1. True;
3. return the value of n (1);

Staying in memory:

Step 11

This value is readily substituted into fibonacci(3), leaving:

Step 12

The value of fibonacci(3) will then be worth 1+1 = 2, being replaced by fibonacci(4):

Step 13

But again you need the value of fibonacci(2), then:

1. the function fibonacci is called with parameter n = 2;
2. check if n is less than or equal to 1. False, execute o else;
3. return the value of fibonacci(1) + fibonacci(0);

Getting on memory:

Step 14

We already know that fibonacci(1) will return 1 and fibonacci(0) will return 0, so for simplicity, I will put its values directly at fibonacci(2):

Step 15

Making the value of fibonacci(2) equal to 1+0 = 1, being readily substituted into fibonacci(4):

Step 16

Thus, the value of fibonacci(4) will be equal to 2+1 = 3, being promptly replaced in fibonacci(5):

Step 17

To still calculate the final value of fibonacci(5) you need the value of fibonacci(3):

1. the function fibonacci is called with parameter n = 3;
2. check if n is less than or equal to 1. False, execute o else;
3. return the value of fibonacci(2) + fibonacci(1);

That is, the value of fibonacci(3) will be fibonacci(2) + fibonacci(1):

Step 18

Parsing from left to right again calculates the value of fibonacci(2):

1. the function fibonacci is called with parameter n = 2;
2. check if n is less than or equal to 1. False, execute o else;
3. 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, so replacing the values:

Step 20

Resulting in fibonacci(2) equal to 1+0 = 1, being readily substituted into fibonacci(3):

Step 21

Still need to calculate the value of fibonacci(1), which we already know is worth 1:

Step 22

Thus, the value of fibonacci(3) will be 1+1 = 2, being readily substituted into fibonacci(5):

Step 23

Finally, the value of fibonacci(5) will be worth 3+2 = 5, being promptly replaced at resultado:

So when it runs:

resultado = fibonacci(5)

The value of resultado will be 5. This value that can be proven by running the code.

See working on Ideone .

Recursion is a function that has a defined basis, in the case of Fibonacci was that fib(1) = 1, and fib(0) = 0, for if n <= 1, return n. If the argument passed to the function is not equal to base it calls the function itself with modified parameters, such as fib(n-1) + fib(n-2), it does this process until the value given as argument is equal to base. When finally it finds the base values, it starts to solve wheels the functions that were called.

For example, to solve fib(5):

• fib(5) calls fib(4) and fib(3)

• fib(4) calls fib(3) and fib(2)

• fib(3) calls fib(2) and fib(1)

• fib(2) flame fib(1) + fib(0), then we find the base.

Replacing

fib(5) = fib(4) + fib(3) = 

( fib(3) + fib(2) ) + ( fib(2) + fib(1) ) =

( ( fib(2) + fib(1) ) + ( fib(1) + fib(0) ) ) + ( ( fib(1) + fib(0) ) + fib(1) )

( ( ( fib(1) + fib(0) ) + fib(1) ) + ( fib(1) + fib(0) ) ) + ( ( fib(1) + fib(0) ) + fib(1) )

Now that it is possible to determine all values, we replace with numbers:

( ( 1 + 0 ) + 1 ) + ( 1 + 0 ) ) + ( ( 1 + 0 ) + 1 )

( ( 1 + 1 ) + 1  ) + ( 1 + 1 )
( 2 + 1) + 2
3 + 2
5

So fib(5) is 5

Man, I have had difficulty in fibonacci also, it is the following, I recommend to create two variables, one that receives the current value and another that receives the previous value and all this you put in a repeating structure, I did with For, follows below a fibonacci that I did using VISUALG in Portuguese.

insira o código aqui algoritmo "semnome"

var

c,fi, ant, at: inteiro

inicio

at <- 1

ant <- 0

para c <- 1 ate 15 faca

fi <- at + ant

ant <- at

at <- fi

escreva(fi)


fimpara


fimalgoritmo

If you have any doubts, just ask

A recursive function is more or less a function that calls another only that in the case it works like this:

Example Code:

def fatorial (n):
    if n <= 0:
        return n
    else:
        return n*fatorial(n-1)

Explanation: What is really happening is I pass a value to min even and save it and pass that value(-1) again and take the old one and multiply with the new one until I no longer pass value to min even though I can pass another value to someone else.