Recursion tightens JavaScript code

When a function calls itself, that's recursion. It can be tough to master, but it's important to learn how to use it the right way. Here's a look at how to use recursion to tighten your code.

Like a number of languages derived from C, JavaScript supports recursion—a function either directly or indirectly calling itself. If a function directly calls itself, that function is said to be recursive. If the recursion takes place in a group of functions, they’re said to be mutually recursive.

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!

The nonrecursive version of this function, shown in Listing B, is significantly longer than the recursive version in Listing C.

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.

This is a JavaScript implementation of the Quicksort algorithm, which was invented in 1960 by C. A. R. Hoare. Quicksort works by splitting the array into two parts and then sorting them separately. Each part is then passed to Quicksort, where the process begins again and continues until the array has been sorted. It is important to note here that JavaScript considers arrays as objects and therefore passes them to the called function by reference, so that any changes made to the array are made to the actual array and not a copy.

Recursion strengths
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.

Recursion weaknesses
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.

When the Internet was new, memory was limited and modems were slow. Tightly written code was a way to conserve limited resources. Today, resources aren’t as limited as in the past, but there is no reason to abandon tightly written code. Although considered an advanced concept, recursion can be used to reduce the size of JavaScript functions.


Editor's Picks