DEV Community: Oliver Schmidt

George and Robert walk into a bar...

Oliver Schmidt — Sun, 14 Jul 2024 16:46:47 +0000

Update (October 19, 2025): Removed the historical sections about George Boole and Robert Recorde as they distracted from the main topic.

The title might sound like there is only a joke waiting here for you (an SEO desaster, I know). Sorry to disappoint. The story is that George Boole gave us Boolean logic, Robert Recorde gave us the equals sign — and ES2021 combined them into JavaScript's logical assignment operators.

Understanding Logical Assignment Operators

Logical assignment operators are syntactic sugar in JavaScript that combine assignment (=) with a logical (&&, ||) or nullish coalescing (??) operator. There are three types:

Logical AND Assignment (&&=): Assigns the value on the right to the variable on the left only if the left variable is truthy.
Logical OR Assignment (||=): Assigns the value on the right to the variable on the left only if the left variable is falsy.
Nullish Coalescing Assignment (??=): Assigns the value on the right to the variable on the left only if the left variable is null or undefined.

Logical AND Assignment (`&&=`)

The &&= operator is a shortcut for setting a variable's value only if it currently holds a truthy value. It's particularly useful in scenarios where an action should only proceed if a certain condition remains true.

Example Use Case: Feature Toggle

Imagine a scenario where certain features should only be enabled for administrators:

const isAdmin = user.isAdmin();
let canAccessDashboard = isAdmin;

canAccessDashboard &&= user.isAuthenticated();
console.log(canAccessDashboard); // true if user is authenticated, otherwise false

This code snippet ensures that canAccessDashboard is only true if both isAdmin and user.isAuthenticated() are true, effectively guarding the feature behind two conditions.

Logical OR Assignment (`||=`)

The ||= operator allows you to assign a value to a variable if the variable currently holds a falsy value (e.g., null, undefined, 0, false, ""). This is incredibly useful for setting default values.

Example Use Case: Setting Defaults

const userSettings = {
  theme: null,
};

// Set default theme if none is specified
userSettings.theme ||= "dark";
console.log(userSettings.theme); // Outputs 'dark'

This operator is ideal for initializing variables that have not been set, ensuring that your application uses a sensible default without overwriting potentially meaningful falsy values like 0 or false.

Nullish Coalescing Assignment (`??=`)

The ?? operator, known as the nullish coalescing operator, is a relatively recent addition to programming languages. It's not a logical assignment operator in the strict sense, even though the ES2021 specification classifies it as such, since it's not based on a logical operator. Instead, its development is more closely tied to the practical needs of programming, particularly in handling null and undefined values in a clean and predictable manner.

The ??= operator is used to assign a value to a variable if and only if the variable is currently null or undefined. This is more precise than the ||= operator, which also considers other falsy values.

Example Use Case: Configuration Defaults

const config = {
  timeout: 0,
};

config.timeout ??= 5000; // Set default timeout if not specified, i.e. undefined, or null
console.log(config.timeout); // Outputs 0, preserving the explicitly set falsy value

This operator is particularly useful in configurations and settings where defaults should only fill in missing values without replacing other falsy but valid settings like 0.

Practical Benefits and Considerations

Using logical assignment operators, instead of if or ternary statements, reduces the amount of code you need to write, and can make your intentions clearer to other developers. As with many features, the key is to use these operators judiciously, especially when dealing with falsy values that are valid in your code's context.

Additional Note

There are more assignment operators in JavaScript, like the left shift assignment operator (<<=). Those seem less widely applicable to me but might be worth another post at some point...

(Cover image on top by starline on Freepik)

:where() :is() my mind?

Oliver Schmidt — Fri, 28 Jun 2024 14:54:17 +0000

Update (October 19, 2025): Removed the CSS Nesting section as it contained an inaccuracy about specificity behavior and distracted from the main topic of the post. Added practical use cases for :is() and :where() to the Complex Selectors section.

In CSS, pseudo-classes like :hover and :first-child apply styles mostly based on an element's state or position. There are also "functional pseudo-classes," among which :not is the oldest and very likely still the most well-known. However, :is() and :where() are two less popular ones that also allow for simplifying complex CSS selectors. In this post, I will explore how these pseudo-classes work.

And if now you're still a bit curious about the title of this post, the pseudo-classes discussed give me a unique opportunity to reference The Pixies in a technical article...

Understanding `:is()`

The :is() pseudo-class simplifies the process of writing complex selector patterns in CSS. The question whether you should be using such patterns in the first place is another one. I'm briefly gonna come back to that later. For now simply consider the following CSS rules where you want to apply the same styles to various elements within article sections:

article h1 a,
article .example a,
article #unique a {
  color: darkblue;
}

Using :is(), this can be streamlined into:

article :is(h1, .example, #unique) a {
  color: darkblue;
}

This not only reduces redundancy but also enhances readability. But there is one more thing: it's important to understand how :is() interacts with CSS specificity:

Specificity in `:is()`

Specificity determines which styles are applied when more than one rule could apply to an element. It's calculated based on the types of selectors used in a CSS rule:

ID selectors are the most specific (count as 100).
Class selectors (.example), pseudo-classes (like :disabled), and attribute selectors (like a[href*="example"]) are less specific (count as 10 each).
Type selectors (like h1) and pseudo-elements (like ::first-line) are the least specific (count as 1 each).

When using the :is() pseudo-class, the specificity of the :is() selector itself is considered to be the specificity of the most specific selector inside its parentheses. This means that it adopts the highest specificity value from its arguments.

In the example above, the specificity of the :is() selector is determined by the highest specificity among the included selectors, which in this case is the ID selector #unique with a specificity count of 100. Therefore, the entire rule article :is(h1, .example, #unique) a will have a specificity count of 102 (100 from #unique, 1 from article and 1 from a).

This configuration means that even though h1 and .example have lower individual specificities (1 for type selectors and 10 for class selectors, respectively), within the :is() they effectively adopt the specificity of #unique, which is 100.

Consequently, any CSS rule targeting article :is(h1, .example, #unique) a will have a higher specificity than other rules targeting article h1 a or article .example a alone, even if those rules are defined later in the CSS. This higher specificity applies unless those competing rules also include an ID selector or are within a higher specificity context.

Exploring `:where()`

The :where() pseudo-class functions very similarly to :is(), with one crucial difference: it has 0 specificity. Using the same set of selectors, we can rewrite the example like this:

article :where(h1, .example, #unique) a {
  color: darkblue;
}

Specificity in `:where()`

The specificity calculation for CSS rules using :where() is straightforward. The original first rule, article h1 a, has a specificity of 1 from the element selector h1 plus 1 from each of the element selectors (article and a), totaling a specificity of 3. In contrast, this rule inside :where(), article :where(h1) a, maintains a specificity of 2, which comes solely from the element selectors article and a. This is because the :where(h1) part contributes zero to the specificity.

Therefore, if both rules target the same a within an h1 element within article, the original rule with higher specificity will override the second rule. This setup illustrates how :where() allows for the application of styles that remain easy to override, making it a potential choice for applying broad, default styles that can be easily customized or overridden elsewhere in the stylesheet.

Complex Selectors in Modern CSS

Earlier in this article, I hinted at the question of whether using complex CSS selectors is advisable in the first place. While they are powerful tools, they carry inherent challenges. It can be difficult to manage them in large projects, as they often lead to brittle CSS that is hard to refactor. And while modern browsers are optimized for CSS parsing, overly complex selectors can still impact rendering performance, particularly in large DOM structures. Additionally, managing specificity with complex selectors, as seen with :is(), can become cumbersome. This often leads to "specificity wars", where styles unintentionally override each other due to conflicting specificity levels.

The landscape of styling in web development has significantly evolved over the last decade. Several modern methodologies and tools allow you to build complex UIs while making it easier to avoid these pitfalls:

BEM encourages a flat structure with minimal nesting and specificity, making styles easier to read and maintain. It significantly reduces the risk of unintended style overrides and enhances modularity.
CSS Modules are particularly useful in component-based architectures like React or Vue, where they allow for the local scoping of CSS by automatically creating a unique class name for each style. This method avoids global scope issues and helps in maintaining modular and reusable components without the fear of styles bleeding across components.
CSS-in-JS also scopes styles to components, reducing global conflicts and specificity issues, and offers dynamic styling capabilities based on state or props.
Utility-First frameworks, such as Tailwind CSS, provide a vast set of utility classes that can be composed directly in the HTML. This minimizes the need for custom CSS and complex selectors.
Component Libraries come with a set of pre-designed and pre-styled components that can be directly used in projects, though they can also be headless. They help standardize UI elements across applications and reduce the need for custom CSS.

Even if complex selectors should be minimized, :is() and :where() remain useful in some cases. For instance, use :where() for base styles or starters that need to stay easy to override, and :is() to group shared interaction states like :hover and :focus without repetition.

(Cover image on top by Maik Jonietz on Unsplash)

Time, Space and Complexity

Oliver Schmidt — Wed, 17 Apr 2024 15:43:37 +0000

Introduction
Big O Notation
Time Complexity: The Speed of Execution
Space Complexity: The Memory Usage
Tail Call Optimization: A Special Case
Dynamic Programming: A Potential Optimizer
Conclusion

Introduction

In my previous article on recursion and backtracking, we delved into a coding kata, exploring both a pure recursive solution and a dynamic programming approach. To keep the focus on understanding these concepts, I sidestepped the realm of time and space complexity for the most part. These are important aspects when evaluating the efficiency of algorithms, and while they were silently at work in the examples I discussed, they didn't take the spotlight. Now, it's time to bring these to the forefront.

Admittedly, discussing the time and space complexity of solutions to a coding kata might seem a bit contrived, as these considerations typically come into play for more complex tasks, such as developing sophisticated algorithms. Yet, it provides an opportunity to explain these concepts in a more accessible context.

And while the title might also suggest a foray into astrophysics, rest assured, we'll be sticking to the realm of computer science. The only space we'll be exploring is the one in your computer's memory...

Big O Notation

Before we dive into the complexities of the pure recursive and dynamic programming solutions, let's take a moment to understand Big O notation. Now, my own background in computer science isn't steeped in formal education, and I understand that many of you might be in the same boat. So, I won't - and frankly, couldn't - dive too deep into its formal definitions and mathematical underpinnings.

Big O notation is a way to express the efficiency of an algorithm in terms of both time and space. The "O" in the notation stands for "Order of", and it's used to describe how the resource requirements of an algorithm grow as the size of the input increases. In the context of the kata example, this means that n - which represents the number of parentheses we need to balance - is getting larger.

When we talk about the number of operations an algorithm performs, we're discussing its time complexity. In the context of algorithmic analysis, "operations" refer to the fundamental steps to solve a problem, such as comparisons, arithmetic operations, or assigning values.

Similarly, when we consider the amount of memory an algorithm uses, we're referring to its space complexity.

The expression inside the parentheses, such as O(1), O(n), or O(n^2), describes the relationship between the size of the input (usually denoted as 'n') and the resource being measured. For example, O(1) indicates constant time or space, meaning the algorithm's performance or memory usage does not change with the size of the input. O(n) suggests linear growth, and O(n^2) indicates quadratic growth, which can quickly become inefficient as the input size grows.

When discussing the efficiency of algorithms, it's also useful to be aware of the term "polynomial complexity", which applies to both time and space requirements. And here we have to get a bit more mathematical I'm afraid.
Polynomial complexity is represented as O(n^k), where n is the size of the input and k is a fixed number known as the constant exponent. This means that the time or space needed by the algorithm grows at a rate proportional to the input size n raised to the power of k. This is generally more manageable than exponential complexity, such as O(2^n), where the resources needed can increase dramatically with the size of the input. Lower-degree polynomial complexities, like linear O(n) or quadratic O(n^2), are usually efficient for large inputs. However, as the degree of the polynomial (k) increases, the resource requirements grow accordingly, which can lead to decreased efficiency for very large inputs. Despite this, polynomial complexities are often sought after in the design of algorithms because they offer a reasonable compromise between the ability to handle complex problems and maintaining computational practicality.

Here is a visualization of the efficiency of different algorithmic complexities, as referenced from the Big O Cheat Sheet:

For those interested in exploring further, you can find more examples of common function orders here. But be aware that most of these examples are quite mathematical in nature.

It's important to note that Big O notation describes the upper limit of the resource usage in the worst-case scenario. An algorithm with a time complexity of O(n) might not always take exactly n steps to complete, and one with a space complexity of O(n) might not use exactly n units of memory, but these are the maximums we can expect.

To determine the complexity of a given algorithm, you need to analyze both the operations it performs and the memory it utilizes, as these factors contribute to its time and space complexity, respectively. For instance, if an algorithm processes each element of an input array once, its time complexity is O(n), where n is the size of the array. Conversely, if the algorithm must allocate an additional array of the same size, its space complexity would also be O(n). If the algorithm compares each element with every other element, resulting in nested loops, its time complexity becomes O(n^2), reflecting the n^2 pairs of comparisons for an array of size n. Similarly, if the algorithm needs to store a unique result for each pair, the space complexity would also be O(n^2).

In practice, determining an algorithm's complexity is often a multifaceted task that extends beyond mere operation counts. It requires a deep understanding of the algorithm's structure, mathematical analysis, and occasionally, advanced concepts from theoretical computer science, such as the properties of specific number sequences like Catalan numbers.

And now, a word of caution regarding what follows below... As I'm neither a computer scientist nor mathematician, I consulted Large Language Models (LLMs) to analyze the algorithms and determine the time and space complexity of both the pure recursive and dynamic programming solutions. While LLMs can provide educated estimates, they are not perfect. The complexities provided by these models are based on my careful questioning of them. Despite my best efforts to extract accurate information, I cannot guarantee the absolute correctness of these complexities. Therefore, the results should be considered a helpful reference for understanding the performance of these solutions rather than an indisputable fact.

Time Complexity: The Speed of Execution

Time complexity refers to how the duration of an algorithm's execution grows with the increase in the size of the input. As mentioned above, it's usually expressed using Big O notation.

Consider the pure recursive solution from my previous article.

function balancedParens(n) {
  if (n === 0) {
    return [""];
  }

  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;
}

This function systematically explores each possibility for arranging n pairs of parentheses through recursive calls. The time complexity for this algorithm is O(4^n / sqrt(n)). But what does this mean without getting into the weeds of mathematics?

In the simplest terms, the 4^n part of O(4^n / sqrt(n)) suggests that the number of different combinations the function has to check is growing exponentially - every time we add another pair of parentheses, the number of possibilities multiplies. However, the division by sqrt(n) (the square root of n) indicates that this growth is somewhat offset as n gets larger. Altogether, we can consider this complexity to be similar to O(2^n) as explained and visualized above.

To illustrate with examples, let's look at the cases where n = 1 and n = 2:

For n = 1, there's only one pair of parentheses to place, resulting in just one combination: (). The time complexity for this specific case is O(4^1 / sqrt(1)), which calculates to O(4). This indicates that the function will perform 4 operations when there is only one pair of parentheses.
For n = 2, there are two pairs of parentheses, which can be arranged in two ways: (()) and ()(). The time complexity for this specific case is O(4^2 / sqrt(2)), which simplifies to O(16 / 1.41), or approximately O(11.31). In this instance, the function is expected to perform roughly 11 operations, which is more than double the operations for n = 1, illustrating the exponential increase in the number of operations as n increases.

Remember, these calculations are approximations meant to give you a sense of how the function's runtime grows. They're not exact figures, but they help us understand the efficiency without diving into complex math.

It's natural to wonder if a different approach could yield better performance or complexity. However, the time complexity of generating all combinations of balanced parentheses is inherently exponential. This is because there are 2^(2n) combinations in total. Therefore, achieving a polynomial time complexity for this problem is not possible. This is a fundamental aspect of the problem itself, not a limitation of the specific approach used. So, while we can strive to optimize our solution as much as possible, we cannot escape the exponential nature of this problem.

Space Complexity: The Memory Usage

While time complexity gives us an idea of how long an algorithm will take, space complexity tells us how much memory it will use. Just like time complexity, space complexity can be expressed using Big O notation, which helps us understand how memory usage grows with the size of the input. When analyzing the space complexity of an algorithm, it is important to consider both the auxiliary space and the space used by the input.

Auxiliary space is the additional memory that an algorithm uses beyond the input size. This includes memory allocated for variables, data structures, and the stack frames in recursive calls. This space is temporary and can be reclaimed after the algorithm's execution.

The space used by the input refers to the memory occupied by the input data itself, which remains constant for a given set of inputs and does not change with the algorithm's internal workings. When comparing the space complexity of two algorithms, the size of the input is often similar, which allows the space used by the input to be disregarded for the comparison.

Consequently, the comparison focuses on the auxiliary space, which can vary based on the algorithm's implementation and is subject to optimization. Therefore, while the total space used by an algorithm includes both auxiliary space and the space used by the input, space complexity analysis and comparisons between algorithms typically emphasize the auxiliary space.

In the case of the pure recursive solution, the space complexity is O(n). This is because the maximum number of frames, or layers, on the call stack at any point is proportional to the number of pairs of parentheses n. However, the actual maximum height of the call stack will be 2n due to the nature of the problem, where we must place n opening and n closing parentheses to form a valid combination. For a detailed illustration of how the call stack changes during the execution of the pure recursive solution, please refer to the walkthrough section of my previous article.

Each recursive call to generate adds a new frame to the call stack, which includes the function's local variables, parameters, and return address. The memory used by these frames accumulates, contributing to the total space complexity of the algorithm. This is why deep recursion can lead to high memory usage, and in extreme cases, a stack overflow error if the call stack exceeds the amount of memory allocated to it.

Tail Call Optimization: A Special Case

Tail call optimization (TCO) is a technique that can improve the performance of recursive functions, particularly in terms of space complexity. In a tail-recursive function, the recursive call is the last operation in the function. This means that when the function makes the recursive call, it doesn't need to do any more computation after the call returns. Some programming languages or compilers can optimize these calls to avoid adding a new stack frame for each call, which can significantly reduce the space complexity and prevent stack overflow issues.

However, the support for TCO varies across different programming languages. Languages like Scheme, Haskell, and Scala have full support for TCO, meaning they can optimize any tail-recursive function. On the other hand, languages like Python and Java do not support TCO.

The ECMAScript 2015 (ES6) standard introduced the concept of "proper tail calls" (PTC), which mandates that compliant JavaScript engines must implement TCO for tail calls. PTC ensures that a function call in tail position does not increase the call stack size, thus allowing for potentially infinite recursive calls in constant stack space.

Despite being part of the ES6 specification, the adoption of PTC in JavaScript engines is very limited. As of now, JavaScriptCore, the engine behind WebKit browsers like Safari, is the only engine that fully supports PTC (available in strict mode). V8, which powers Chrome and Node.js, had implemented PTC but ultimately decided against shipping the feature. More information on the decision can be found in the V8 blog post.

The proposal of "syntactic tail calls" to provide an explicit syntax for tail calls, co-championed by committee members from Mozilla (responsible for SpiderMonkey, the engine of Firefox) and Microsoft, was a response to these concerns. However, this proposal is now listed among the TC39's inactive proposals, possibly due to diminished interest, which may stem from the infrequent use of tail recursive functions in JavaScript.

In the absence of widespread engine-level support for PTC, developers have explored language-level solutions to achieve tail call optimization. The fext.js library offers a method for managing tail calls in JavaScript, while the Babel plugin for tail call optimization provides transformations for tail-recursive functions during the build process. These tools are also not widely adopted though.

The original pure recursive solution, as shown above, is not tail-recursive because it does not return the result of the recursive call directly. Instead, the function concludes with the operation of returning the final result, after all recursive calls have been made and their outcomes have been aggregated.

To illustrate a tail-recursive style, we can rewrite it:

function balancedParens(n) {
  if (n === 0) {
    return [""];
  }

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

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

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

    return result;
  };

  return generate("", 0, 0, []);
}

In this version, the result array is passed through each call to generate, and the function is structured to return the result of the recursive call directly whenever possible. Should PTC be available in the execution environment, the space complexity would be reduced to O(1). This is because the same stack frame would be reused for each recursive call, which eliminates the need for additional memory for each call and maintains a constant stack depth. In any case, it's good to be aware of this technique when working with recursive functions.

Dynamic Programming: A Potential Optimizer

The dynamic programming solution to the parentheses problem incrementally builds solutions for larger sets of parentheses, such as ()(), based on the solutions for smaller sets, like ().

const balancedParens = n => {
  if (n === 0) {
    return [""];
  }

  let parentheses = [];

  for (let i = 0; i < n; i++) {
    for (let left of balancedParens(i)) {
      for (let right of balancedParens(n - 1 - i)) {
        parentheses.push(`(${left})${right}`);
      }
    }
  }

  return parentheses;
};

This method uses memoization to store solutions to previously solved subproblems, enhancing efficiency by avoiding redundant calculations. This is an improvement over the pure recursive approach, which recalculates solutions for each subproblem. And, while theoretically being more space-intensive than pure recursion, the use of memoization is justified by gains in computational speed, especially for larger problems.

The efficiency of our dynamic programming solution is captured by the time complexity O(n^2 * C_n). In this formula, C_n stands for the nth Catalan number. Now, the Catalan number for a specific n tells us how many different ways we can arrange n pairs of balanced parentheses. It's a special sequence of numbers that Eugène Charles Catalan figured out follows a particular pattern, making it easier to predict the number of arrangements without having to list them all out. You can use a Catalan number calculator to verify this.

To give a practical example of how O(n^2 * C_n) plays out, let's consider n = 2 again, which means we're looking for combinations of two pairs of parentheses: (()) and ()(). The Catalan number for n = 2 is 2, reflecting these two possibilities. Now, if we plug n = 2 into our time complexity formula, we square the n to get 4, and then multiply by the Catalan number, which gives us 4 * 2 = 8. So, for n = 2, the dynamic programming solution is expected to perform roughly 8 operations to find all valid combinations. This is in contrast to the pure recursive approach, which doesn't remember past solutions and would perform more operations as n increases.

Regarding space complexity, the dynamic programming solution requires storage for each unique combination of balanced parentheses it computes. The amount of storage correlates with the nth Catalan number for each n, leading to a space complexity of O(n * C_n). This stands in comparison to the pure recursive approach’s space complexity of O(n), attributed to the recursion stack’s depth. While the dynamic programming method requires more space due to memoization.

Conclusion

While recursive solutions can be simple and elegant, they may be inefficient in terms of time complexity due to redundant calculations and can also consume significant memory with deep call stacks.

Tail call optimization can improve the space efficiency of some recursive functions, but it's not universally applicable and is not supported by all programming languages or compilers.

Dynamic programming can optimize time complexity by eliminating redundant work, but this often comes at the cost of increased space complexity due to storing subproblem results. Additionally, dynamic programming can be more complex and harder to understand than pure recursion.

Theoretically, the choice between using pure recursion or dynamic programming depends on the nature of the task at hand and the constraints one is facing, particularly whether optimizing for time or space is more critical. In reality, it's probably mostly a matter of experience or preference. Usually, only if issues arise do we think about our solutions more formally. And even then, most programmers do not typically apply Big O notation, unless they are working on something significant, like the React DOM diffing algorithm maybe. Instead, we measure actual performance to pinpoint bottlenecks. But a prior awareness of time and space complexity can certainly be valuable here. And if we want or have to take it a step further, leveraging LLMs can assist us in determining the complexity of a given solution, as well as helping us find a more performant one.

(Cover image on top by Andy Holmes on Unsplash)

Of recursion and backtracking

Oliver Schmidt — Tue, 12 Dec 2023 10:22:15 +0000

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): Made a 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) {
  if (n === 0) {
    return [""];
  }

  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)