Understanding recursive method for factorial

[TechSupportGeek]

Hello, what the title says, I'm really confused with recursion. I understand the basics like what we actually call a recursive method (a method that calls itself within its body) but I can't seem to understand how it is used (especially the factorial example). OK, the following example is the classic recursive way to find the factorial of a number. I will write the code (pseudo-code) and then tell you what I can't seem to understand. BTW, sorry if my English ain't that good, I'm neither English nor American.

int fact(int n)
{
	if (n == 1) return 1;
	else return fact(n - 1) * n;
}

First things first, I know the factorial of a number is given by the following math expression: n! = 1 * 2 * 3 * ... * (n - 1) * n (as an example) which leads us to this expression: n! = (n - 1)! * n (which is used in the code above). So what I don't understand is if we actually have the method call itself with parameter n - 1 before the operation (*) is evaluated, how we get the factorial of the number. The way I see things, constantly calling fact(n - 1) when the method tries to return will result in an infinite amount of times the method being called without returning anything. Also, I thought that when the return statement was used, something must actually be returned to the point in the code where the method is called (eg. int fact = fact(5); will result in variable "fact" being assigned to 120). I would so much appreciate it if you could break it down for me step by step, what exactly happens when the method calls itself again that is. Do you think you can help me?

P.S: The question may sound kinda dumb to you but I'm a 15 year old self taught programmer who hasn't been taught functions let alone factorials at school as of yet so it is harder for me to understand. Again, keep it simple if you can.

Thank you in advance.

[deceptikon]

The way I see things, constantly calling fact(n - 1) when the method tries to return will result in an infinite amount of times the method being called without returning anything.

Each call invokes a new instance of the function with new arguments. The effect is as if you did this:

int fact1()
{
    return 1;
}

int fact2()
{
    return fact1() * 2;
}

int fact3()
{
    return fact2() * 3;
}

int fact4()
{
    return fact3() * 4;
}

int fact()
{
    return fact4() * 5;
}

Recursion just makes the syntax for that process simpler.

[TechSupportGeek]

This made it a bit more clear for me but I still don't get the whole picture (not understanding fully). Also, what do you mean by "a new instance of the function"? Is it possible that multiple instances of a function can exist?

[TechSupportGeek]

Never mind, I think I got it now. It basically keeps calling the method until n is equal to 1 as we have set the IF condition and then it reverse evaluates the factorials until it reaches the factorial of 4 and then finally multiply it by 5 in order to give 120. Could you tell me if I'm going in the right direction? :)

[deceptikon]

Is it possible that multiple instances of a function can exist?

Yes:

fact(5);
fact(5);

Those are two instances. It would help to learn how function calls are typically handled if you don't know already. Knowing about the call stack helps to differentiate between definition of a function and execution of it at run time.

It basically keeps calling the method until n is equal to 1 as we have set the IF condition and then it reverse evaluates the factorials until it reaches the factorial of 4 and then finally multiply it by 5 in order to give 120.

Well, I can't say that's wrong. :)

[TechSupportGeek]

OK thank you very much for your help! I may have a look at the call stack article. Thread solved!