The factorial function

The best example to illustrate recursion is the factorial function. Factorials are calculated by multiplying a number by each successive integer less than itself, but greater than zero. For example, the factorial of 5 (5!) is calculated by the following expression:

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

To understand the recursive factorial function, you have to be able to make the conceptual leap from the previous statement to this statement:

5 ! = 5 * 4! = 5 * 4 * 3! = 120

The progression outlined above can be written as: 

x ! = x * (x-1)!

This statement lends itself well to an elegant recursive solution. To calculate the factorial of a given number, you can multiply the value by the factorial of the number minus 1, as long as the number is not equal to one. If the value of the number is one, stop the recursion process. In code, the function looks like: 

function factorial(x)
{
if(x==1)
	return 1;
else
	return (x * factorial(x-1));
}

When factorial() is called, with the value of 3, for example, the function first checks to see if the argument is equal to 1. In this case, it is not, so the next step returns the value of 3 * factorial(3-1). Before this value can be returned to the calling program, the value of factorial(3-1) must be calculated. The function factorial(2) returns (2 * factorial(2-1)). Finally, the function factorial(1) returns the value of one. Once this value is returned, the next function above it -- factorial(2) -- can evaluate the expression (return 2 * 1). This result is then sent to the original function call -- factorial(3) -- and that function can evaluate the expression return (3 * 2).

Like a loop, a recursive function must move to an ending scenario, and have a statement to end the recursive calls. However, there are some dangers to using recursion, as crash.htm (found in the examples following this section) illustrates.

Calling functions takes a finite amount of time, and a program that relies heavily on recursive function calls will suffer from an (albeit minimal) performance degradation. Further, the internal tracking of recursive function calls uses large amounts of system resources and memory.

The last time I wrote a program like CRASH.HTM, it brought the whole system down. These days, both Netscape Navigator and Microsoft Internet Explorer have improved memory management, so only the script crashes, and an error is reported. With 32M of RAM on my home system, I can make approximately 165 and 245 recursive function calls in Navigator 3 and IE3 respectively, and more with the latest versions. Funnily enough, if we believe what IE3 reports, it has enough memory to store the number infinity, but not 250 recursive function calls!