Determine the nth Fibonacci term with recursion

Asked

Viewed 5,555 times

8

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
  • 5

    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?

  • You don’t understand recursion or Fibonacci?

  • 2

    You know how to test your table?

  • 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 if the answer cleared your doubt, you can accept it by pressing the icon on the left side of it.

4 answers

20

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:

inserir a descrição da imagem aqui

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:

inserir a descrição da imagem aqui

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:

inserir a descrição da imagem aqui

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:

inserir a descrição da imagem aqui

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:

inserir a descrição da imagem aqui

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:

inserir a descrição da imagem aqui

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:

inserir a descrição da imagem aqui

Step 6

Thus, having the value of fibonacci(1), this is replaced by fibonacci(2):

inserir a descrição da imagem aqui

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:

inserir a descrição da imagem aqui

Step 8

This value is promptly replaced in the value of fibonacci(2):

inserir a descrição da imagem aqui

Step 9

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

inserir a descrição da imagem aqui

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:

inserir a descrição da imagem aqui

Step 11

This value is promptly replaced in fibonacci(3), getting:

inserir a descrição da imagem aqui

Step 12

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

inserir a descrição da imagem aqui

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:

inserir a descrição da imagem aqui

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):

inserir a descrição da imagem aqui

Step 15

Leaving the value of fibonacci(2) equal to 1+0 = 1, being promptly replaced in fibonacci(4):

inserir a descrição da imagem aqui

Step 16

Thus the value of fibonacci(4) is equal to 2+1 = 3 and is promptly replaced in fibonacci(5):

inserir a descrição da imagem aqui

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):

inserir a descrição da imagem aqui

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:

inserir a descrição da imagem aqui

Step 19

As we already know, fibonacci(1) is worth 1 and fibonacci(0) is worth 0, then replacing the values:

inserir a descrição da imagem aqui

Step 20

Resulting in fibonacci(2) equal to 1+0 = 1, being promptly replaced in fibonacci(3):

inserir a descrição da imagem aqui

Step 21

The value of fibonacci(1), that we already know is worth 1:

inserir a descrição da imagem aqui

Step 22

Thus the value of fibonacci(3) will be 1+1 = 2 and is promptly replaced in fibonacci(5):

inserir a descrição da imagem aqui

Step 23

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

inserir a descrição da imagem aqui

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.

  • 5

    If you want to try to simplify the tables leaving less large and thus taking out a lot of space. Another option is to paste images instead of text.

3

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

0

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

  • 1

    So man, since I’m a programming beginner and I’m following the exercises of a book, I would have to understand specifically about how this exercise behaves, to then get references of how to do the same thing only in a different way, you know? but I appreciate the attempt !

  • Got it, man, but blz, keep studying

  • @Joãovictorcarvalho, can you format the pseudocode better? Only by four spaces before the code line, indenting internal blocks (all commands within the block para-faça-fimpara highlighted more to the right than the outside code)

0

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.

Browser other questions tagged

You are not signed in. Login or sign up in order to post.