Hello and welcome to our community! Is this your first visit?
Enjoy an ad free experience by logging in. Not a member yet? Register.

# Thread: I can't understand why this works

1. ## I can't understand why this works

function factorial (\$n) {
if (\$n==0) return 1;
return factorial (\$n - 1) * \$n;
}

This is messing with my brain. It's a function to come up with the factorial of a given number (5 = 1*2*3*4*5). And it works. But I can't understand why.

Say \$n = 4

it will try to return [factorial (3) * 4], but what is factorial (3)? How can it know that without knowing what the sublayers are?

If you go all the way down to factorial (1-1) you get a value of 1 returned. And 1 * 4 = 4 so it would return 4. So the next layer up we have

factorial(4-1) which is the same as factorial (3) which requires another loop. I'm so lost my head is spinning!!! Am I looking at this completely wrong?

2. You're doing a recursive function, which is a function that calls itself. Fortunately, you've given it a way to escape, (by checking to see if \$n==0), thus avoiding an endless loop .

Within PHP, the function accumulates as it calls itself over and over again. When it finally is kicked out (return equals 'true', or '1' in your case), it simply returns the accumulated value. So there are some things happening there that you can't see (within PHP). It is what it is.

3. Yeah, I got that much. I just don't understand how this is actually playing out. I never would have come up with that or thought it would come up with a factorial!

4. I would not have thought of it either.

I would have done it using more lines of code.

It's magic.

Here's a page that describes recursive. And your factorial example is part of the discussion:
Recursive Functions

C++ has the same accumulative properties within recursive functions.

5. If you go all the way down to factorial (1-1) you get a value of 1 returned. And 1 * 4 = 4 so it would return 4. So the next layer up we have
That is not correct. Using factorial(1) will result in factorial(0) * 1 or 1 * 1, not 1 * 4. Each step of \$n is cycled down to nothing:
• factorial(4); \$n = 4; return factorial (4 - 1) * 4;
• substack: factorial(3); \$n = 3; return factorial (3 - 1) * 3;
• substack: factorial(2); \$n = 2; return factorial (2 - 1) * 2;
• substack: factorial(1); \$n = 1; return factorial (1 - 1) * 1;
• substack: factorial(0); \$n = 0; escape clause: return 1;
• return stack: 1
• return stack: (1) * 2 = 2
• return stack: (2) * 3 = 6
• return stack: (6) * 4 = 24

Does that help to clear it up? The key here is that the value of \$n cycles down to nothing which is why the escape clause is used. So the highest function on the stack will never have the \$n = 4, that's only reserved by the lowest in the stack. Note as well that recursive functions are never necessary, and you can perform the same task using loops which will almost definitely be more efficient (there will be a threshold which determines this, but it is quite low). Recursive functions are more useful for convenience in small recursions than for large cycles.

PHP has a limited stack size compared to a language like C, but you can certainly do a few hundred levels before the stack will topple.

6. Thank you for that explanation! That makes me feel better

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•