Click here to Skip to main content
15,867,704 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Hello,

I have a doubt about how the following recursion works:


What I have tried:

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 itself works.
Could somoeone please clarify me this doubt?

Thanks very much.
Posted
Updated 7-Feb-23 7:50am
v3

To add to what Richard has said ...
Think of recursion as a set of Russian Dolls (or Matryoshka Dolls)[^] Each contains within it another Matryoshka until you get to smallest possible. To access each, you open the doll and extract the next size down.

Your function just implementing the string definition of a factorial:
5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1
So from that: when N is greater than 1, return N * factorial(N - 1). Otherwise, return 1

So your fact function checks if N is 1 and returns 1 if so, otherwise it multiplies N by (N - 1) factorial by calling itself. The (direct or indirect) "function calling itself" bit is called recursion, and it's a powerful technique - though not often used in practice as it has some significant problems in the real world.
Run it through the debugger and you'll see what I mean.

As a recursion demonstration using factorials works, but it's really a poor example of recursion: a loop would have been a lot more efficient.
 
Share this answer
 
The code has a number of steps:
1. The print statement calls the fact function passing in the value 4.
2. The fact function checks the value od the passed in parameter:
2. If the parameter is equal to 1, then it returns that value.
3. If the value is not equal to 1:
3a. It calls itself passing the prameter value minus 1 (i.e first time it passes 3)
3b. On return it multiplies the returned value by the original.
4. It then returns that number to the caller.

So when the passed in value reaches 1 it returns to the caller, and that causes the other return statements to be called. So you get the returned values multiplied together: 4 * 3 * 2 * 1 = 24.

If you step through the code with the debugger you can see it in action.
 
Share this answer
 
Comments
CPallini 7-Feb-23 12:43pm    
5.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900