How this recursive function (factorial function) behaves in Python

Asked

Viewed 725 times

1

I don’t understand how the code behaves after it leaves the recursive function on line 7, fat = n * fatorial(n-1), i.e., how the code assigns the value to the variable n of this line and how is done the calculation of this line where the code assigns its value to the variable fat?

Note: I am self-taught.

#!/usr/bin/python

def fatorial(n):                             #linha1
    print("Calculando o fatorial de %d" % n) #linha2
    if n==0 or n == 1:                       #linha3
        print("Fatorial de %d = 1" % n)      #linha4
        return 1                             #linha5
    else:                                    #linha6
        fat = n * fatorial(n-1)              #linha7
        print(" fatorial de %d = %d" % (n, fat) ) #linha8
    return fat                              #linha9

fatorial(4)
  • 2

    In this reply i explain how a recursive function is executed for calculating factorial in Javascript. The logic is exactly the same and may be useful for you.

  • 2

    Possible duplicate of Recursiveness in Python

1 answer

1

It’s a little complex to explain but I’ll try.

  • The factor(4) function is called:
  • Factorial(4) execution "hangs" when it needs to calculate fatorial(4-1);
  • A new call is made to the function fatorial in another scope with the value of n being 3. This new so-called "lock" in the same place because it is now necessary to calculate the value of fatorial(2). This happens until the execution flow reaches the point of calculating the fatorial(1), which RETURNS the value 1.
  • Now the function FRAME fatorial(2) gets the return value to replace fatorial(2-1) and the execution continues.
  • The print statement is executed and the returned variable is now the fat with the value of 2.
  • Therefore when the function fatorial(2) was executed, the value returned was 2.
  • This value will be replaced in the fatorial(3) in row 7, and so on.

To understand how this function works it is necessary to have knowledge about the scope of variables and frames of functions.

Try to access this site here, it will help you understand: link

  • 1

    until the part that the code left the recursive function I understood, what I didn’t understand is how the variable "n" that is between the sign of = and the sign of * in the #line7 behaves to assign the value to the variable fat, understand? I don’t think I understand. NOTE: I already use this link to understand the behavior of the codes I’m studying, but thanks for the xD warning

  • 1

    I didn’t fully understand the code, but I appreciate the effort in trying to help, thanks friend! ;D

  • The variable "n" will have a value in each frame. First it has value 4 (when it is called factorial(4)) then it is called factorial(3) and "n" then it has value 3 and so on. Remember that each function call a new instance of "n" is created, that is, you have 4 instances with different values of "n" created in your program.

  • I guess I get it, every call of the recursive function is like the main function has several nested functions of its own, right? and at each call of these "nested functions" were to decrease the n-1 value of the recursive functions, correct me if I’m wrong, I think this is it!

  • 1

    if I understood what you meant, that’s right. Several instances of "n" are created, one each scope, one for each call of the factorial(n) function. Each 'n' independent of the other, with different value and "live" only during the execution of the recursive call. If you have solved your question mark as "answered" my question to give that strength

Browser other questions tagged

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