Web Turtle - Factorial Example

Here's how a factorial function works. The factorial of a number (say, 5) is that number times the previous factorial (so 5! = 5 * 4!). The special case is 0!, whose factorial is simply 1.

In other words,

  5! = 5 * 4!
           4! = 4 * 3!
                    3! = 3 * 2!
                             2! = 2 * 1!
                                      1! = 1 * 0!
                                               0! = 1

So, working from the bottom right, back up to the top left:

  5! = 5 * 24 = 120
           4! = 4 * 6 = 24
                    3! = 3 * 2 = 6
                             2! = 2 * 1 = 2
                                      1! = 1 * 1 = 1
                                               0! = 1

What if we wanted to know what "6!" was? That's simple! It's just 6 * 5! (six times 5 factorial), or: 6 * 120. That turns out to be 720.

---

This is what "factorial" might look like, written in the C programming language:

  int factorial(int v)
  {
    if (v == 0)
      return 1;
    else
      return v * factorial(v - 1);  /* factorial() calls itself! */
  }

To find the factorial of 5, you'd do the following in C:

  n = factorial(5);
  /* n now contains 5! */

---

And finally, here's what it looks like in WebTurtle, using the "POP" and "PUSH" commands to simulate the local variable 'v' that we get in C:

# FACTORIAL

  IF V == 0

    ; The factorial of 0 ("0!") is simply 1; we're done!
    LET V 1

  ELSE

    ; Push the current 'V' onto the stack, so we can pop it back later
    PUSH V

    ; Now call the 'FACTORIAL' procedure again, with V-1...
    LET V V-1
    GO FACTORIAL

    ; Retrieve the factorial of V-1, and temporarily store it in vriable 'A'
    LET A V

    ; Get the original V off of the stack
    POP V

    ; The answer (to this particular call of 'FACTORIAL')
    ; is that V! is V * (V-1)!
    LET V V*A

  ENDIF

RETURN

Notice that before the recursive "GO" call to "FACTORIAL" (and before the value of "V" is changed to "V-1", to be "sent" to the recursive call) the command "PUSH V" sticks the value of "V" on the stack.

After the call, the "returned" value now stored in "V" is copied into "A" in the "LET A V" command. "V" is popped off of the stack, and then set to the value of "V*A" to be returned to the previous call of "FACTORIAL" or used by the main program, where it first called the "FACTORIAL" procedure.

To find the factorial of 5 in WebTurtle, you'd do the following:

  LET V 5
  GO FACTORIAL
  ; V now contains 5!, or 5 * 4 * 3 * 2 * 1, which is 120