Recursion

Recursion is an important programming technique. It's used to have a function call itself from within itself. One handy example is the calculation of factorials. The factorials of 0 and 1 are both defined specifically to be 1. The factorials of larger numbers are calculated by multiplying 1 * 2 * ..., incrementing by 1 until you reach the number for which you're calculating the factorial.

The following paragraph is a function, defined in words, that calculates a factorial.

"If the number is less than zero, reject it. If it isn't an integer, round it down to the next integer. If the number is zero or one, its factorial is one. If the number is larger than one, multiply it by the factorial of the next smaller number."

To calculate the factorial of any number that is larger than 1, you need to calculate the factorial of at least one other number. The function you use to do that is the function you're in the middle of already; the function must call itself for the next smaller number, before it can execute on the current number. This is an example of recursion.

Clearly, there is a way to get in trouble here. You can easily create a recursive function that doesn't ever get to a definite result, and cannot reach an endpoint. Such a recursion causes the computer to execute a so-called "infinite" loop. Here's an example: omit the first rule (the one about negative numbers) from the verbal description of calculating a factorial, and try to calculate the factorial of any negative number. This fails, because in order to calculate the factorial of, say, -24 you first have to calculate the factorial of -25; but in order to do that you first have to calculate the factorial of -26; and so on. Obviously, this never reaches a stopping place.

Thus, it is extremely important to design recursive functions with great care. If you even suspect that there's any chance of an infinite recursion, you can have the function count the number of times it calls itself. If the function calls itself too many times, however many you decide that should be, it automatically quits.

Here's the factorial function again, this time written in JScript code.

function factorial(aNumber)  {
aNumber = Math.floor(aNumber);  // If the number is not an integer, round it down.
if (aNumber < 0)  {  // If the number is less than zero, reject it.
    return "not a defined quantity";
    }
      if ((anumber == 0) || (anumber == 1))  {  // If the number is 0 or 1, its factorial is 1.
      return 1;
      }
        else return (anumber * factorial(anumber - 1));  // Otherwise, recurse until done.
}