Can someone explain this recursion problem to me? (Factorial)

Question

Edit - I have solved this problem but if its okay, I would like the experts here to still explain this problem so that other beginners could learn. You would do a way better job explaining.

I'm trying to learn recursion and I kind of get the idea of recursion (dividing a big problem into smaller solutions and then combining them together. I have a few questions about this particular problem though. Factorial.

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

The problem is, I don't know exactly how the calculation has been done after we reduce the n value by 1 on every recursion. For example, if n = 5, then the n value would go down by 1 every time (5,4,3,2,1). What I don't get is, what happens with those values? When are they actually multiplied up together? Can someone write the output or what's happening to the n value maybe step-by-step? I have tried to visualize this on PythonTutor, it was helpful but not very helpful.

If you guys feel as if this is a repeated question or very common, please link me to a source like (Youtube) where this is explained. Thank you very much.

Answer 1

to answer your question, i first need to bring you attention to two things that might happen in the program. of course the Code under the IF and the code under the ELSE. Keep it in your mind for now.

let's look at your questions : what happens with those values? When are they actually multiplied up together?.

now let's assume we have n = 3, so let's read the code under ELSE BLOCK (since n != 1) and see what happens.

we have return n*fact(n-1) and since n = 3, --> return 3*fact(3-1)

and here is where you might start to see it, after this block and returning 3*fact(3-1) nothing really gets calculated, you need to understand that THE IF STATEMENT is there for a reason. because if we don't have that IF BLOCK OF CODE we won't stop the recursion i.e : it will always return the function fact(...).

so what happens incrementally:

• fact(n=3) : n != 3 , (ELSE BLOCK), return 3*fact(3-1)
• fact(n=2) : n != 2 , (ELSE BLOCK), return 3*2*fact(2-1)
• fact(n=1) : n == 1 , (IF BLOCK), return 1 (we return 1 instead of 1 so we stop and calculate all)

fact(n=3) = 3 * 2 * 1 = 6

to sum up, what happens with those values, they get stacked together until last return statement (IF STATEMENT), then they get calculated.