1

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. enter image description here

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.

Hakari Kinji
  • 33
  • 5
  • If you already have a solution, it's possible to add an answer to your own question as well. – D Malan Oct 24 '22 at 09:04
  • Does this answer your question? [Understanding how recursive functions work](https://stackoverflow.com/questions/25676961/understanding-how-recursive-functions-work) – VLAZ Oct 24 '22 at 09:04
  • @DMalan I understand but since my knowledge on recursion is a bit wonky, it would be better coming from someone who understands better and explains better. – Hakari Kinji Oct 24 '22 at 10:53

3 Answers3

1

This recursion has its termination condition at n = 1. This means it returns a constant value at n=1 and will not start another recursive call. If the n is > 1 it will return n*fact(n-1).

The calls for fact(5):

  • 5*fact(4)
  • 5*(4*fact(3))
  • 5*(4*(3*fact(2)))
  • 5*(4*(3*(2*fact(1))))
  • 5*(4*(3*(2*1)))
Fexo
  • 179
  • 7
1

The first if condition is trivial, since 1! = 1, (I would've used if n<=1, since also 0! = 1). If the number N is greater than 1, the function returns that number multiplied by the result of the same function for N-1, so the function will iter over all integers until it gets to 1.

Suppose N=3:

  • the if condition goes into the else part, since 3>1
  • what the function return is 3 * fact(2), but what is fact(2)? is a function that returns 2 * fact(1), since 2>1
  • so at the end what you get in return is 3 * 2 * fact(1), and knowing that fact(1) returns 1 (you activate the if condition), you obtain 6=3!

Hope this helped

imburningbabe
  • 742
  • 1
  • 2
  • 13
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.

Axtin
  • 38
  • 3