Walden Systems Geeks Corner Recursion in JavaScript tutorial programming developer Rutherford NJ New Jersey NYC New York North Bergen County

Recursion in JavaScript

a high-level, interpreted programming language that conforms to the ECMAScript specification. It is a language that is also characterized as dynamic, weakly typed, prototype-based and multi-paradigm. Alongside HTML and CSS, JavaScript is one of the three core technologies of the World Wide Web.[9] JavaScript enables interactive web pages and thus is an essential part of web applications. The vast majority of websites use it,[10] and all major web browsers have a dedicated JavaScript engine to execute it.

Recursion is a programming pattern that is useful in situations when a task can be naturally split into several tasks of the same kind, but simpler. Or when a task can be simplified into an easy action plus a simpler variant of the same task. Or dealing with certain data structures. When a function solves a task, in the process it can call many other functions. A partial case of this is when a function calls itself. That's called recursion.

An obvious use case for recursion is solving x^y, we can use a for loop to implement this or we can use iteration. With iteration, the code is much simpler because it calls itself with the results. Below are examples of implementing power using for loop and recursion. Note how the recursive variant is fundamentally different. When recursion is called, the execution splits into two branches, one to call itself again and the other to return the value.

For loop implementation

function pow(x, n) 
{
  let result = 1;

  for (let i = 0; i < n; i++) 
  {
    result *= x;
  }

  return result;
}

Iteration

function pow(x, n) 
{
  if (n == 1) 
  {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

Limitations in JavaScript

The maximum recursion depth is limited by JavaScript engine. We can make sure about 10000, some engines allow more, but 100000 is probably out of limit for the majority of them. There are automatic optimizations that help alleviate this, but they are not yet supported everywhere and work only in simple cases. That limits the application of recursion, but it still remains very wide. There are many tasks where recursive way of thinking gives simpler code, easier to maintain.

Execution stack

Let's look at the inner workings of recursion. The information about a function run is stored in its execution context. The execution context is an internal data structure that contains details about the execution of a function. Where the control flow is now, the current variables, the value of this, and few other internal details. One function call has exactly one execution context associated with it.

When a function makes a nested call, it triggers a series of events. The current function is paused. The execution context associated with it is remembered in a special data structure called execution context stack. The nested call executes. After it ends, the old execution context is retrieved from the stack, and the outer function is resumed from where it stopped. To do a nested call, JavaScript remembers the current execution context in the execution context stack.