Doubt about recursion

Python
1

Hello,

I have a doubt about how the following recursion works:

’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’

def fact(n):


if n==1:
    return 1
else:
    return n*fact(n-1)


print(fact(4))

’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’

The output is 24, which is the factorial of 4.

I know thath Python has a built-in function which is math.factorial(). But in this case, how is “fact” interpreted as the factorial calculator? I think I’m not understanding how recursion it self works.
Could somoeone please clarify me this doubt?

Thanks very much.

2

you seem to have an indentation problem in the code.
I believe the indentation you need is:

def fact(n):
  if n == 1:
    return 1
  else:
    return n * fact(n-1)

print(fact(4))

Looking at this, we can see there is a function being defined called fact which takes the param n.
Then it proceeds to call itself (fact(n-1)) recursively each time with a smaller value of n until n reaches 1 at which point it returns a 1.

So in the call stack we would expect to see something like:
print
fact(4)
fact(3)
fact(2)
fact(1)

1 Like
3

In case it helps, here was an answer I gave to recursion once, might help with understanding(its javascript though)… more important, some others included tool links that allow you to enter your python code and watch the process.

1 Like
4

Thanks,

So in this case, we would multiply all the numbers inside the parenthesis:
fact(4)…n =4
fact(3)…3 = n-1 =4-1
fact(2)…2 = n-1 = 3-1
fact(1)…1 =n-1 = 2-1

And the output would be 4x3x2x1 = 24?

5

each call to fact does exactly what the if statement is saying it will do.
it checks to see if its version of n is 1
if not, it executes the else

the else does the multiplication of the current number n with whatever fact(n-1) gives us

6

This code defines a recursive function “fact” that calculates the factorial of a given number “n”.

The base case for the recursion is when n is 1, in which case the function returns 1. In other cases, the function returns the current value of “n” multiplied by the factorial of “n-1”, which is calculated by calling the “fact” function recursively with “n-1” as the argument.

In the example you provided, the call to “fact(4)” will trigger the following sequence of calls:

  • fact(4) returns 4 * fact(3)
  • fact(3) returns 3 * fact(2)
  • fact(2) returns 2 * fact(1)
  • fact(1) returns 1

The final result of 24 is obtained by combining the results of all these calls, as each return value is multiplied by the previous “n”.

7

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.