JavaScript And Recursion

Recursion is an age old concept used in mathematics when an object is defined by other objects of the same type.  A real life example would be the mirrors in a department store dressing room. If you look in the right spot, you can see both reflections repeating themselves in each other. 

Each iteration of your image grows smaller and smaller into infinity. In computer science recursion happens when a solution to a problem is resolved by computing smaller instances of the same problem.  In JavaScript, recursion boils down to a function calling itself to solve a problem.

This concept can be tough to grasp, but taking the time to learn how to code recursively provides many benefits. Sorting methods can be sped up immensely using recursion.  An example of this is C. A. R. Hoare’s “Quicksort” pattern, which was developed in the 1960’s. If coded correctly, methods utilizing recursion are shorter and take up less bandwidth.  Another benefit is better methods for combinational searches. And many mathematical induction methods run faster and are simpler to code using recursion, for example computing factorials.

Calling JavaScript Recursion Directly

There are two ways to code recursive functions in JavaScript: first by directly calling the function from within itself and second by using an indirect call.

Here’s an example of how to call the function directly:

function recursMe(param) {
     if (param < 0) {     //base case
         return -1;
      }
     else {

          //some code here
          recursMe(param);
      }
}

A common pitfall of having a function call itself are infinite loops. When writing a recursive function, the base case must be carefully planned to avoid causing an infinite loop. The base case is the terminating condition or the “stopper” of the loop. In the example above, the base case is if(param <0). Until this case returns ‘true’, the recursion continues.

If the base case never returns ‘true’, the function is stuck in an infinite loop and the program never ends until the computer runs out of memory and crashes. One way to avoid causing an infinite loop is to build in a default stopping point or exit condition.  For example, if the function runs 10 times then it automatically exits.

Calling JavaScript Recursion Indirectly

Next let’s look at calling a javascript recursive function indirectly:

function recursMe(param) {
     if (param < 0) {	//base case
          return -1;
     }
     else {

          //some code here
          setTimeout(“recursMe(“ + param + “)”, 1);
     }
}

When calling the next recursion using the setTimeout() function, the page will not lock up while the entire recursion processes. The user will be able to continue scrolling the page, and other processes can continue to run.

The syntax of setTimeout is:

timeoutId = setTimeout([script-to-execute], [time-in-milliseconds]);

setTimeout() returns the id or handle to the timer that was executed which can later be used to cancel the execution of the function by using the clearTimeout(timeoutId), if necessary.

Calling recursive functions indirectly also helps to alleviate the potential for a stack overflow error.  These errors can occur when a recursion uses up the stack allocated by the web browser.  The various web browsers vary greatly in the amount of stack that is allocated to their javascript engines, from Safari which only allocates around 500 up to Chrome which will allocate over 21,000. Every time your recursive function is called directly a copy of the function’s variables is added to the stack. As the functions finish processing the variables are removed from the stack.

In the case of Safari, if that stack hits 501, the user will get a stack overflow error and the page will not function properly.

Summary

In summary, using javascript recursive functions is a great solution for many web page problems, such as sorting or mathematical induction.  Depending on your solution, you may want to call the recursion directly or you may find using the indirect method is better for your page.  Either way, you must avoid all possible scenarios that could cause an infinite loop and watch out for possible stack overflows.

Happy Coding!