Of recursion and backtracking

Update (December 17, 2023): Added a new paragraph in the section on dynamic programming to provide a more balanced view of its trade-offs.

Update (January 18, 2024): Updated the dynamic programming section with a solution using proper memoization, and revised the explanation accordingly.

Update (January 19, 2024): Added tiny optimization for the n = 0 case in the recursive solution, which I had forgotten there.

Update (February 20, 2024): Small improvement in the dynamic programming section.

Introduction
Recursion and Backtracking
The Call Stack
The Kata
Walkthrough
Bonus: Pure Recursion vs. Dynamic Programming
Conclusion

Introduction

Recently, I was working on a coding kata on codewars.com. Early on, I started thinking that a potential solution might utilize recursion, a concept that involves a function calling itself. However, I quickly realized that my grasp of recursion was not as solid as it needed to be for this task. In this post, I will share the insights gained from deepening my understanding of recursion while working through the kata.

Recursion and Backtracking

Recursion and the related concept of backtracking are techniques in computer science used to solve complex problems by breaking them down into simpler subproblems.

Recursion involves a function calling itself with different arguments until it reaches a so called base case. The base case is a condition that signals the function to stop calling itself and start returning. It’s the simplest possible version of the problem, one that can be solved directly without any further recursive calls. The base case is crucial in recursion as it prevents infinite recursion and allows the function to terminate at a certain point. We will revisit this concept in the practical part of this article, which should provide a clearer understanding of what it means and how it works.

Backtracking, on the other hand, involves exploring all possible solutions to a problem and, when a dead end is reached, “backtracking” to a previous step and trying a different path. These techniques are often used in combination to solve problems in areas such as combinatorics, parsing, and artificial intelligence. They’re particularly useful for problems where the solution involves exploring all possible combinations or permutations of a set of elements.

One prominent example of a task that can be effectively solved using recursion is the mathematical puzzle known as the Tower(s) of Hanoi. It involves moving a stack of disks from one peg to another following certain rules. Notably, Douglas Crockford referenced this puzzle in his book “JavaScript: The Good Parts” to explain recursion.

The Call Stack

In JavaScript, the call stack is a key component of the event loop, which is the engine that drives JavaScript’s single-threaded, non-blocking, asynchronous behavior. The call stack, recursion, and backtracking are all interconnected. When a function is called in JavaScript, it’s added (or “pushed”) onto the call stack. If that function calls another function, the new function is pushed onto the top of the stack and becomes the currently executing function. This “Last In, First Out” (LIFO) structure of the call stack is what allows recursion to work. Each recursive call adds a new layer to the stack, and when a base case is reached, the functions start returning and are “popped off” the stack one by one. This is where backtracking comes into play, allowing the program to explore different paths or solutions. The event loop continuously checks the call stack and processes functions based on the LIFO principle. Once the stack is empty, it means that all functions have finished executing.

The Kata

To better understand how these techniques work in practice, let’s take a closer look at the aforementioned kata which involves generating all possible combinations of a set of parens:

Write a function which makes a list of strings representing all of the ways you can balance n pairs of parentheses.

Examples:
balancedParens(0) => [""]
balancedParens(1) => [”()“]
balancedParens(2) => [”()()”,”(())“]
balancedParens(3) => [”()()()”,”(())()”,”()(())”,”(()())”,”((()))”]

As hinted at above, this is a classic example of a problem that can be solved using recursion and backtracking.

Our strategy will be to build all combinations of parentheses from scratch, starting with an empty string and adding one parenthesis at a time. We’ll keep track of the number of open and close parentheses we’ve added so far to ensure that we only add valid combinations.

To do this, we’ll use a recursive function, which we’ll call generate. This function will take the current combination of parentheses, and the number of open and close parentheses.

The function will add an open parenthesis if we haven’t used up all the open parentheses, and a close parenthesis if it doesn’t exceed the number of open parentheses. This ensures that we don’t end up with any unbalanced combinations like ((()). If we’ve used up all the open and close parentheses, we have a valid combination, which we’ll add to our list. If not, we’ll continue to add parentheses by making recursive calls to generate.

codwars provides an empty balancedParens function accepting one argument, n, representing the pairs of parenthesis to balance. We’re gonna put our generate function inside of it:

function balancedParens(n) {
  let result = [];
  const generate = (current, open, close) => {
    if (current.length === 2 * n) {
      result.push(current);
      return;
    }

    if (open < n) {
      generate(current + "(", open + 1, close);
    }

    if (close < open) {
      generate(current + ")", open, close + 1);
    }
  };

  generate("", 0, 0);

  return result;
}

Walkthrough

Now, let’s walk through the process of how this function works in the context of the kata, using a simple visualization of the call stack. This will give us a clear, step-by-step understanding of how recursion and backtracking unfold in real time.

As to not have too many explanatory steps, but enough to be clear, I’m gonna focus on the n = 2 case.

1. Step

The initial call to the recursive function generate is made with an empty string: generate("", 0, 0). This pushes a new frame onto the call stack. The previously empty stack now looks like this:

- generate("", 0, 0);

The result array is [].

2. Step

This leads to a recursive call with an open parenthesis added: generate("(", 1, 0). This pushes another frame onto the stack:

- generate("(", 1, 0)
  - generate("", 0, 0);

The result array is still [].

3. Step

This call can lead to two recursive calls: one where another open parenthesis is added generate("((", 2, 0) and one where a close parenthesis is added generate("()", 1, 1). Let’s follow the first call where another open parenthesis is added: generate("((", 2, 0). This pushes another frame onto the stack:

- generate("((", 2, 0)
  - generate("(", 1, 0)
    - generate("", 0, 0)

The result array is still [].

4. Step

Now, we can only add close parentheses. The next call is generate("(()", 2, 1). This pushes another frame onto the stack:

- generate("(()", 2, 1)
  - generate("((", 2, 0)
    - generate("(", 1, 0)
      - generate("", 0, 0)

The result array is still [].

5. Step

Finally, we add another close parenthesis: generate("(())", 2, 2). This pushes another frame onto the stack:

- generate("(())", 2, 2)
  - generate("(()", 2, 1)
    - generate("((", 2, 0)
      - generate("(", 1, 0)
        - generate("", 0, 0)

We’ve reached a valid combination "(())", which is added to the result array. The result array is now ["(())"].

This is the base case where the current combination of parentheses has reached the length of 2 * n (since each pair of parentheses contributes two characters to the string). When this condition is met, we know we’ve added all the parentheses we can, and we add the current combination to the result array. This is why we check if current.length === 2 * n at the beginning of each call to generate. If this condition is true, we’ve reached the base case, and we add current to result and return from the function. This is the point at which we stop making new recursive callsfor the current combination and start backtracking.

6. Step

We have now explored all combinations starting with two open parentheses. The call generate("(())", 2, 2) finishes, so its frame is popped from the stack. The stack now looks like this:

- generate("(()", 2, 1)
  - generate("((", 2, 0)
    - generate("(", 1, 0)
      - generate("", 0, 0)