A recursive function is a function that calls itself (by using its own name within its function body). Here's a simple example that shows the principle of recursion. But because the code tells the trouble( ) function to execute repeatedly (like an image reflected infinitely in two opposing mirrors), Flash will quickly exceed its maximum recursion limits, causing an error:
function trouble () {
trouble();
}
A recursive function that calls itself unconditionally, such as trouble( ) does, is said to exhibit infinite recursion (i.e., the function never stops calling itself). Infinite recursion will cause the computer to run out of memory quickly. To prevent this from happening, Flash sets a maximum of 256 levels of recursion, at which point the recursive function call will fail.
Practical recursive functions call themselves only while a given condition is met (thus preventing infinite recursion). Example 9-4 used recursion to count from a specified number down to 1, but obviously that can be accomplished without recursion.
One classic use of recursion is to calculate the mathematical factorial of a number. The factorial of 3 (written as 3! in mathematical nomenclature) is 3 * 2 * 1 = 6. The factorial of 5 is 5 * 4 * 3 * 2 * 1 = 120. Example 9-8 shows a factorial function that uses recursion.
function factorial (x) {
if (x < 0) {
return undefined; // Error condition
} else if (x <= 1) {
return 1;
} else {
return x * factorial(x-1);
}
}
trace (factorial(3)); // Displays: 6
trace (factorial(5)); // Displays: 120
As usual, there is more than one way to skin a proverbial cat. Using a loop, we can also calculate a factorial without recursion, as shown in Example 9-9.
function factorial (x) {
if (x < 0) {
return undefined; // Error condition
} else {
var result = 1;
for (var i = 1; i <= x; i++) {
result = result * i;
}
return result;
}
}
Examples Example 9-8 and Example 9-9 represent two ways of solving the same problem. The recursive method says, "The factorial of 6 is 6 multiplied by the factorial of 5. The factorial of 5 is 5 multiplied by the factorial of 4 . . ." and so on. The nonrecursive method loops over the numbers from 1 to x and multiplies them all together into one big number.
Which approach is better—recursive or nonrecursive—depends on the problem. Some problems are solved more easily using recursion, but recursion can be slower than nonrecursive solutions. Recursion is best used when you don't know how deeply a data structure may be nested. For example, suppose you wanted to list all the files within a subdirectory, including listing all files within any nested subdirectory, ad infinitum. It would be inconvenient to write a general solution that worked for any number of subdirectories without resorting to recursion. A recursive solution might look like this in pseudocode:
function listFiles (directoryName) {
do (check the next item in directoryName) {
if (this item is a subDirectory itself) {
// Recursively call this function with the new subdirectory
listFiles(subDirectoryName);
} else {
// Display the name of this file
trace(filename);
}
} while(there are still items to check);
}
When we consider the XML object the ActionScript Language Reference, we'll use recursion to list all the elements in an XML document.
