Enjoy an ad free experience by logging in. Not a member yet? Register.

Results 1 to 6 of 6

04172014, 06:31 PM #1
 Join Date
 Mar 2013
 Posts
 29
 Thanks
 7
 Thanked 0 Times in 0 Posts
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 (11) you get a value of 1 returned. And 1 * 4 = 4 so it would return 4. So the next layer up we have
factorial(41) 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?
04172014, 06:54 PM
#2
 Join Date
 Jun 2003
 Location
 Cottage Grove, Minnesota
 Posts
 9,633
 Thanks
 8
 Thanked 1,105 Times in 1,096 Posts
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.
Last edited by mlseim; 04172014 at 06:56 PM.
04172014, 09:01 PM
#3
 Join Date
 Mar 2013
 Posts
 29
 Thanks
 7
 Thanked 0 Times in 0 Posts
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!
04172014, 09:42 PM
#4
 Join Date
 Jun 2003
 Location
 Cottage Grove, Minnesota
 Posts
 9,633
 Thanks
 8
 Thanked 1,105 Times in 1,096 Posts
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.
04172014, 11:09 PM
#5
 Join Date
 Sep 2002
 Location
 Saskatoon, Saskatchewan
 Posts
 16,994
 Thanks
 4
 Thanked 2,662 Times in 2,631 Posts
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:If you go all the way down to factorial (11) 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); $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.
Been gone for a few months, and haven't programmed in that long of a time. Meh, I'll wing it ;)PHP Code:
header('HTTP/1.1 420 Enhance Your Calm');
04242014, 03:24 PM
#6
 Join Date
 Mar 2013
 Posts
 29
 Thanks
 7
 Thanked 0 Times in 0 Posts
Thank you for that explanation! That makes me feel better