Recursion and Stack

Recursion is the process in the framework of which a function calls itself, either directly or indirectly. It is especially handy in situations when there is a necessity to split a single task into several simple ones.

Above all, with the help of recursion, you can write quite elegant codes.

To understand better what recursion is, you need to start with something simple. Write a function factorial(n), in Math, a non-negative integer's factorial is the product of all positive integer less than or equal to it. n! denotes the factorial of the integer:

factorial(1) = 1

factorial(2) = 2

factorial(3) = 6

factorial(4) = 24

You can implement it in two ways.

• The first way is iterative thinking that uses the for loop, like this:
• function factorial(n) {
•   var result = 1;
•   for (let i = n; i > 1; i--) {
•     result *= i;
•   }
•   console.log(result);
• }
• factorial(5);
• The second is recursive thinking that is aimed at simplifying the task and calling itself as follows:
• function factorial(n) {
•   if (n <= 1) {
•     console.log(1);
•   } else {
•     console.log(n * factorial(n - 1));
•   }
• }
• factorial(5);
• Note that, as a rule, the recursive solution is shorter than the iterative one. If we rewrite the same and use the conditional operator? instead of if for making factorial(n) compact but still readable, it can look like this:
• function factorial(n) {
•   console.log((n <= 1) ? 1 : (n * factorial(n - 1)));
• }
• factorial(5);

• JavaScript engine limits the maximum depth of recursion. It, usually, should be 10000, but some engines might allow more.

  The Execution Context and Stack¶

  The execution context can be described as an internal data structure containing details about the execution of a function, in which the control flow is now, the current variables, the value of this and other internal details.

  One call of a function has one execution context connected with it.

  When a nested call is made by a function, the following occurs:

  • A pause of the current function.
  • The execution context linked with it is remembered in a unique data structure known as execution context stack.
  • Execution of the nested call.
  • After it finishes, the previous execution context is recovered from the stack. The external function is resumed from where it was interrupted.

  During the factorial(4), happens the following:

  At the start of it, the execution context stores n = 4 variable. The execution flow is at the function’s line 1.

  It looks like this:

  Context: { n: 4, at line 1 } factorial(4)

  The n <= 1, n is 1, and the flow will go on into the second branch of if.

  Here is an example:

• function factorial(n) {

    if (n <= 1) {

      return 1;

    } else {

      return n * factorial(n - 1);

    }

  }

  console.log(factorial(4));

• As the variables are the same, but the line is changed, the context looks like this:

  Context: { n: 4, at line 5 } factorial(4)

  For calculating n * factorial(n - 1), it is necessary to implement a subcall of the factorial with new factorial(3) arguments.

  factorial(3)

  For doing a nested call, JavaScript remembers the present execution context in the execution context stack.

  The factorial function is called. For all the functions, the process is as follows:

  • The present context is remembered on the stack top.
  • For the subcall, a new context is created.
  • When the subcall ends, the old context is popped from the stack. Its execution goes on.

  Below you can see the context stack at the time you enter the subcall factorial(3):

  • Context: { n: 3, at line 1 } factorial(3)
  • Context: { n: 4, at line 5 } factorial(4)

  factorial(2)

  Then you can see the context stack at the time you enter the subcall factorial(2):

  • Context: { n: 2, at line 1 } factorial(2)
  • Context: { n: 3, at line 5 } factorial(3)
  • Context: { n: 4, at line 5 } factorial(4)

  When finishing the subcall- it is easier to restore the old context, as it keeps variables, as well as the precise place where it stopped.

  factorial(1)

  A new subcall is implemented in line 5. The arguments are n=1.

  As a rule, a new execution context is made, and the previous execution is pushed on top of the stack, like this:

  • Context: { n: 1, at line 1 } factorial(1)
  • Context: { n: 2, at line 5 } factorial(2)
  • Context: { n: 3, at line 5 } factorial(3)
  • Context: { n: 4, at line 5 } factorial(4)

  You can notice 3 previous contexts and 1 currently running for factorial(1).

  The Exit¶

  In the process of factorial(1) execution, unlike in the previous situations, n <= 1 is truthy, and the first if branch works. It looks like this:

• function factorial(n) {

    if (n <= 1) {

      return 1;

    } else {

      return n * factorial(n - 1);

    }

  }

• As no nested calls exist, the function ends, returning 1.

  The execution context is not necessary anymore, as the function ends. Therefore, it is deleted from the memory. The previous one is restored:

  Context: {n: 4, at line 5 } factorial( 4)

  After its end, you can have a result of factorial(4) = 24.

  In this case, the depth of the recursion was 4.

  It is essential to follow the memory requirements. For example, a loop-based algorithm can save memory.

  Let’s check out the following example:

• function factorial(n) {

    let result = 1;

    for (let i = n; i > 1; i--) {

      result *= i;

    }

    return result;

  }

  console.log(factorial(4));

• Note that you can rewrite any recursion as a loop. The loop option might be made much more effective.

  Recursive Structures¶

  A recursive data structure can be described as a structure replicating itself into parts. Let’s consider the following case: In an HTML-document, an HTML-tag may contain a list of HTML-comments, text parts, other HTML-tags. It’s a recursive definition. Now, let’s examine another recursive structure, called “Linked list.” It can even become a better alternative for arrays.

  Here is an example:

• let list = {

    value: "a",

    next: {

      value: "b",

      next: {

        value: "c",

        next: {

          value: "d",

          next: null

        }

      }

    }

  };

  console.log(list);

• The alternative code is as follows:

• let list = {

    value: "a"

  };

  list.next = {

    value: "b"

  };

  list.next.next = {

    value: "c"

  };

  list.next.next.next = {

    value: "d"

  };

  list.next.next.next.next = null;

  console.log(list);

• Summary¶

  Recursion is a programming pattern used for calling a function itself. You can use recursive functions for solving tasks in quite elegant ways. Its arguments make the tasks simpler.