9.9 Recursive Functions

ActionScript for Flash MX: The Definitive Guide, 2nd Edition
By Colin Moock
Chapter 9.  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 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.

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

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.

     



    ActionScript for Flash MX. The Definitive Guide
    ActionScript for Flash MX: The Definitive Guide, Second Edition
    ISBN: 059600396X
    EAN: 2147483647
    Year: 2002
    Pages: 780
    Authors: Colin Moock

    flylib.com © 2008-2017.
    If you may any questions please contact us: flylib@qtcs.net