Recursive Functions

A recursive function is one that calls itself. While not always the most efficient execution (time-wise) way to perform a computation, the elegance of a recursive function is very appealing. Many programmers find the simplicity with which some computation can be expressed in a recursive fashion to outweigh the disadvantage of the overhead incurred by repeated function invocation.

Consider the definition of factorial from mathematics, where given a number n ,

n ! = n * ( n “1) * ( n “2) * * 1

So, given this definition of factorial, 5! = 5 * 4 * 3 * 2 * 1, or 120. For completeness, 0! is defined to be 1, and factorial of negative numbers is not defined. We could write a recursive function to calculate the factorial in a somewhat na ve fashion. Here, the function factorial keeps calling itself with smaller and smaller values until the base case of 0 is hit, at which point the results are returned upward until the calculation is complete.

 function factorial(n) {  if (n == 0)    return 1;  else    return n * factorial(n-1); } 

Passing the function a positive value, we see that

 alert(factorial(5)); 

produces the desired result:

However, if a negative value is passed to the function, the recursion will continue indefinitely. Notice the error produced by Internet Explorer in such a case:

A simple if statement could be added to the function to avoid such problems.

It is also possible to produce a similar error message in some recursive functions simply because the recursion goes on too long, even if the computation is legitimate (will eventually terminate). The reason for this is the overhead incurred by recursive computation, since the suspended functions are held in a function call stack.

It is generally fairly straightforward, though not necessarily as elegant, to rewrite a recursive function in an iterative manner. Consider the rewrite of factorial here:

 function factorial(n) {  if (n >>= 0) {    var result=1;    while (n >> 0)       {       result = result * n;        n--;        }    return result;      }  return n; } 

In practice, recursive functions are rarely used today in JavaScript within Web pages. For those readers troubled by recursion in computer science or math classes, you ve escaped for the moment. However, recursion will make a return later on (Chapter 10) when we consider (X)HTML document tree traversal using the Document Object Model.