Recursive Functions (ActionScript: The Definitive Guide)

9.9. Recursive Functions

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 run out of memory, causing an error:

function trouble( ) {
  trouble( );
}

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.

Example 9-8. Calculating Factorials Using 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.

Example 9-9. Calculating Factorials Without Recursion

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;
    }
}

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. You couldn't 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 in Part III, "Language Reference", we'll use recursion to list all the elements in an XML document.