Determine the nth Fibonacci term with recursion

Question

I don’t understand anything about recursive functions, even debugging, is very confusing for me. Someone can explain me in an easy way?

I tried to analyze the following code:

#!/usr/bin/python

def fibonacci(n):                            #linha1
    if n<=1:                                 #linha2
        return n                             #linha3
    else:                                    #linha4
        return fibonacci(n-1)+fibonacci(n-2) #linha5    

fibonacci(5)                                 #linha6

Answer 1

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:

1. The function fibonacci is called with parameter n = 5;
2. It appears that n is less than or equal to 1. False, executes the else;
3. 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:

1. The function fibonacci is called with parameter n = 4;
2. It appears that n is less than or equal to 1. False, executes the else;
3. 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):

1. The function fibonacci is called with parameter n = 3;
2. It appears that n is less than or equal to 1. False, executes the else;
3. 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):

1. The function fibonacci is called with parameter n = 2;
2. It appears that n is less than or equal to 1. False, executes the else;
3. 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):

1. The function fibonacci is called with parameter n = 1;
2. It appears that n is less than or equal to 1. True;
3. 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):

1. The function fibonacci is called with parameter n = 0;
2. It appears that n is less than or equal to 1. True;
3. 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:

1. The function fibonacci is called with parameter n = 1;
2. It appears that n is less than or equal to 1. True;
3. 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:

1. The function fibonacci is called with parameter n = 2;
2. It appears that n is less than or equal to 1. False, executes the else;
3. 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):

1. The function fibonacci is called with parameter n = 3;
2. It appears that n is less than or equal to 1. False, executes the 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

The value of fibonacci(2):

1. The function fibonacci is called with parameter n = 2;
2. It appears that n is less than or equal to 1. False, executes the 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, 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.

Answer 2

Recursion is a function that has a defined basis, in the case of Fibonacci it 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 the base it calls the function itself with modified parameters, for example fib(n-1) + fib(n-2), it does this process until the value given as argument equals the basis. When she finally finds the values of the base, she begins to solve wheels the functions that have been called.

For example, to solve fib(5):

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

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

• fib(3) flame 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 substitute numbers:

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

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

Therefore, the fib(5) is 5

Answer 3

Man, have I ever had a hard time Fibonacci also, is the following, I recommend to create two variables, one that receives the current value and the other that receives the previous value and all this you put in a repeat structure, I did with the For, follows a Fibonacci I did using VISUALG in English.

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 questions, just ask

Answer 4

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

Sample 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 myself and keep it and pass that value(-1) again and take the old and multiple with the new until I do not pass more value to me even if I can pass another value to another person.