PRDV402: Introduction to JavaScript II

Recursion

A function can refer to and call itself. There are three ways for a function to refer to itself:

1. The function's name
2. arguments.callee
3. An in-scope variable that refers to the function

For example, consider the following function definition:

const foo = function bar() {
  // statements go here
};

Within the function body, the following are all equivalent:

1. bar()
2. arguments.callee()
3. foo()

A function that calls itself is called a recursive function. In some ways, recursion is analogous to a loop. Both execute the same code multiple times, and both require a condition (to avoid an infinite loop, or rather, infinite recursion in this case).

For example, consider the following loop:

let x = 0;
// "x < 10" is the loop condition
while (x < 10) {
  // do stuff
  x++;
}

It can be converted into a recursive function declaration, followed by a call to that function:

function loop(x) {
  // "x >= 10" is the exit condition (equivalent to "!(x < 10)")
  if (x >= 10) {
    return;
  }
  // do stuff
  loop(x + 1); // the recursive call
}
loop(0);

However, some algorithms cannot be simple iterative loops. For example, getting all the nodes of a tree structure (such as the DOM) is easier via recursion:

function walkTree(node) {
  if (node === null) {
    return;
  }
  // do something with node
  for (let i = 0; i < node.childNodes.length; i++) {
    walkTree(node.childNodes[i]);
  }
}

Compared to the function loop, each recursive call itself makes many recursive calls here.

It is possible to convert any recursive algorithm to a non-recursive one, but the logic is often much more complex, and doing so requires the use of a stack.

In fact, recursion itself uses a stack: the function stack. The stack-like behavior can be seen in the following example:

function foo(i) {
  if (i < 0) {
    return;
  }
  console.log(`begin: ${i}`);
  foo(i - 1);
  console.log(`end: ${i}`);
}
foo(3);

// Logs:
// begin: 3
// begin: 2
// begin: 1
// begin: 0
// end: 0
// end: 1
// end: 2
// end: 3

Source: Mozilla, https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Functions#recursion
This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.