Recursion
Recursion is an important programming technique that causes a function to call itself. One example is the calculation of factorials. The factorial of 0 is defined specifically to be 1. The factorial of n, an integer greater than 0, is the product of all the integers in the range from 1 to n.
Using Recursion
The following paragraph is a function, defined in words, that calculates a factorial.
"If the number is less than zero, reject it. If it is not an integer, reject it. If the number is zero, its factorial is one. If the number is larger than zero, multiply it by the factorial of the next lesser number."
To calculate the factorial of any number that is larger than zero, you must calculate the factorial of at least one other number. The function must call itself for the next smaller number before it can execute on the current number. This is an example of recursion.
Recursion and iteration (looping) are strongly related—a function can return the same results either with recursion or iteration. Usually a particular computation will lend itself to one technique or the other, and you simply choose the most natural or preferable approach.
Despite the usefulness of recursion, you can easily create a recursive function that never returns a result and cannot reach an endpoint. Such a recursion causes the computer to execute an infinite loop. Here is 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 to calculate the factorial of, for example, -24, you must calculate the factorial of -25. In order to calculate the factorial of -25, you must first calculate the factorial of -26, and so on. Obviously, this never reaches a conclusion.
Another problem that can occur with recursion is that a recursive function can use all the available resources (such as system memory and stack space). Each time a recursive function calls itself (or calls another function that calls the original function), it uses some resources. These resources are freed when the recursive function exits, but a function that has too many levels of recursion may use all the available resources. When this happens, an exception is thrown.
Thus, it is important to design recursive functions with care. If you suspect any chance of an excessive (or infinite) recursion, design the function to count the number of times it calls itself and set a limit on the number of calls. If the function calls itself more times than the threshold, the function can quit automatically. The optimum maximum number of iterations depends on the recursive function.
Here is the factorial function again, this time written in JScript code. Type annotation is used so the function accepts only integers. If an invalid number is passed in (that is, a number less than zero), the throw statement generates an error. Otherwise, a recursive function is used to calculate the factorial. The recursive function takes two arguments, one for the factorial argument and one for the counter that keeps track of the current recursion level. If the counter does not reach the maximum recursion level, the factorial of the original number is returned.
function factorialWork(aNumber : int, recursNumber : int ) : double {
// recursNumber keeps track of the number of iterations so far.
if (aNumber == 0) { // If the number is 0, its factorial is 1.
return 1.;
} else {
if(recursNumber > 100) {
throw("Too many levels of recursion.");
} else { // Otherwise, recurse again.
return (aNumber * factorialWork(aNumber - 1, recursNumber + 1));
}
}
}
function factorial(aNumber : int) : double {
// Use type annotation to only accept numbers coercible to integers.
// double is used for the return type to allow very large numbers to be returned.
if(aNumber < 0) {
throw("Cannot take the factorial of a negative number.");
} else { // Call the recursive function.
return factorialWork(aNumber, 0);
}
}
// Call the factorial function for two values.
print(factorial(5));
print(factorial(80));
The output of this program is:
120
7.156945704626378e+118