Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 6 of 6
  1. #1
    New Coder
    Join Date
    Mar 2013
    Posts
    25
    Thanks
    5
    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 (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
    Master Coder
    Join Date
    Jun 2003
    Location
    Cottage Grove, Minnesota
    Posts
    9,497
    Thanks
    8
    Thanked 1,089 Times in 1,080 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; 04-17-2014 at 06:56 PM.

  • #3
    New Coder
    Join Date
    Mar 2013
    Posts
    25
    Thanks
    5
    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!

  • #4
    Master Coder
    Join Date
    Jun 2003
    Location
    Cottage Grove, Minnesota
    Posts
    9,497
    Thanks
    8
    Thanked 1,089 Times in 1,080 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.

  • #5
    God Emperor Fou-Lu's Avatar
    Join Date
    Sep 2002
    Location
    Saskatoon, Saskatchewan
    Posts
    16,987
    Thanks
    4
    Thanked 2,660 Times in 2,629 Posts
    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.
    PHP Code:
    header('HTTP/1.1 420 Enhance Your Calm'); 

  • #6
    New Coder
    Join Date
    Mar 2013
    Posts
    25
    Thanks
    5
    Thanked 0 Times in 0 Posts
    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
    •