When coding a recursive function, it’s imperative to include a termination condition—a way for the termination to stop. Without a termination condition, the function will continue to call itself, consuming more and more resources (and time) until an error occurs and the function terminates. In my opinion, factorial is one of the best functions to illustrate a termination condition. Factorial, written as n!, multiplies a whole number n by itself and every whole number between itself and 1. So, 5! equals 5 X 4 X 3 X 2 X 1, or 120. Listing A shows a recursive implementation of the factorial function.
Note the termination condition: 1 is returned when intN is less than or equal to 1. For all other values of intN, the returned value is intN X (intN – 1) factorial, which is where recursion comes into play. I can’t stress enough the importance of the termination condition. It’s easy to get carried away when writing a recursive function and forget the termination condition. But forgetting the termination condition is the equivalent to driving a car with no brakes. It will eventually stop—just not in the manner that you want.
Why use recursion?
The big question is why to use recursion when there are nonrecursive methods that work just as well to perform the same task. One reason is that recursive functions have a tendency to be shorter, and when bandwidth is an issue, shorter functions are better. An example of this size discrepancy is the function to compute an individual number in a Fibonacci sequence.
Origins of recursion
The origin of Fibonacci numbers dates back to 1202 and deals with how fast rabbits could breed under ideal circumstances. Starting with a newborn breeding pair of rabbits in a field, assume that rabbits can mate at the age of one month and that the result is always another breeding pair.
By the end of the second month, there are two pairs of rabbits. By the end of the third month, the original pair produces another pair of rabbits giving a total of three pairs. In the fourth month, the second pair kicks into production, resulting in five pairs. Although the bunnies get off to a slow start, they quickly make up for lost time. Consider that after 25 years, there would be 222,232,244,629,420,445,529,739,893,461,909,967,206,666,939,096,499,764,990,979,600 pairs of rabbits!
In addition to illustrating recursion, Listing B demonstrates an alternative way for a function to refer to itself. The line
return(arguments.callee(intN – 1) + arguments.callee(intN – 2));
could also be written
return(fibonacci(intN – 1) + fibonacci(intN – 2));
By coding the reference as arguments.callee(x) instead of the traditional fibonacci(x), the capability exists to nest the function within another without resulting in an error.
A real-world example
Although the Fibonacci number example serves to show the size difference between nonrecursive and recursive functions, Fibonacci numbers are pretty useless when developing Web applications. Listing D provides a more practical example of recursion—a recursive multidimensional array sort function.
The real strength of recursion is in situations where a problem can be solved by solving smaller versions of the same problem, as in the functions shown above. Certain applications readily lend themselves to recursion, such as parsing an XML document. A well-formed XML document is, for all practical purposes, a tree data structure, which typically can be solved by solving smaller versions of the same problem. The transversal of tree structures can be broken down to examining the current node, repeating the process for each child node in the tree.
It would be wrong to tout the benefits of recursion without listing some of the drawbacks as well. First, thinking recursively takes practice. Although iteration comes naturally, recursion does not. The second problem with recursion is that it is resource intensive. Each recursive function call has just as much overhead as any nonrecursive function call. The third and most important recursion weakness is the stack. The stack is used to store the calling function’s state so that when the called function has terminated, processing returns to the caller. A stack overflow error occurs when there’s an attempt to push the calling function’s state, but there is no space remaining in the stack.