Category: Fundamentals

Recursion Explained in JavaScript

Image generated using Google Gemini

Recursion is a programming technique where a function calls itself to solve a particular problem. It’s especially effective for problems that can be divided into smaller, similar subproblems. By breaking down a complex problem in this way, recursion can often lead to elegant and concise solutions.

A recursive function repeatedly calls itself with smaller versions of the problem until it reaches a simple, solvable base case. This self-referential approach is a powerful tool for tackling problems that have a recursive structure.

A Real-Life Analogy of Recursion

Photo by Alicia Christin Gerald on Unsplash

While the concept can be challenging to grasp, recursion can be likened to solving a jigsaw puzzle. Some puzzle solvers might start by connecting a few pieces together that have similar colors, and they might do so until they have a few groupings of puzzle pieces. They might then connect those groupings into one larger grouping. This strategy can go on until the entire puzzle is completed.

Recursion Fundamentals

For some, it can be easier to learn by reading code, but before we can demonstrate recursion by programming out an example, we need to explain some fundamental concepts of recursion.

In recursion, “cases” are the different scenarios that dictate how a recursive function behaves. These cases logically guide the function on whether to continue recursing or to terminate. Correctly identifying and implementing these cases is essential to ensuring that a recursive function works as intended and doesn’t fall into an infinite loop.

There are typically two primary cases in recursion: the base case and the recursive case.

Base Case

The base case is the condition under which the recursive function stops calling itself. It is the simplest instance of the problem that can be solved directly without further recursion, and it is critical because it prevents infinite recursion by providing a stopping point. The base case stops the recursion when the problem has been reduced to its simplest form or has reached the end of the sequence.

Recursive Case

The recursive case is the condition under which the function continues to call itself with modified arguments. In these scenarios, the function makes progress towards the base case by simplifying or reducing the problem with each recursive call. The recursive case helps to break the problem into smaller sub-problems that have the same structure as the original problem, but with simpler or reduced inputs.

Recursion in JavaScript

Let’s recreate the Math.pow method, which calculates the power of a number, using recursion in JavaScript. The Math.pow(base, exponent) function computes the result of raising thebase value to the power of an exponent.

Recursive Math.pow Implementation

To implement this method using recursion, we’ll use two main cases:

  1. Base Case: If the exponent is 0, the result is 1 because any number raised to the power of 0 is 1.
  2. Recursive Case: Multiply the base by the result of the function with the exponent decremented by 1.

Here’s the JavaScript implementation:

function recursivePow(base, exponent) {
  if (exponent === 0) {
    return 1;
  } else if (exponent < 0) {
    return 1 / recursivePow(base, -exponent);
  } else {
    return base * recursivePow(base, exponent - 1);
  }
}

Explanation of the Code

  1. Base Case: If the exponent is 0, the function returns 1. This stops the recursion from continuing indefinitely.
  2. Edge Case: If the exponent is negative, the function inverts the base (i.e. calculates 1 / base) and calls itself with the positive value of the exponent. This allows the function to correctly compute the result for negative exponents.
  3. Recursive Case: If the exponent is positive and greater than 0, the function multiplies the base by the result of calling itself with the exponent decremented by 1. The decrementing by one is critical because this causes the recursive calls to home in on base case (i.e. reducing the exponent by 1 until it reaches 0).

How the Recursion Unfolds

A flow diagram visualizing a recursive implementation of Math.pow

Let’s walk through an example where we invoke the recursive power function with a base of 2 and a power of 3 (recursivePow(2, 3)). Note, in the illustration above, I’ve omitted the edge case logic for visual clarity.

  1. recursivePow(2, 3) returns 2 * recursivePow(2, 2)
  2. recursivePow(2, 2) returns 2 * recursivePow(2, 1)
  3. recursivePow(2, 1) returns 2 * recursivePow(2, 0)
  4. recursivePow(2, 0) returns 1 (base case)
  5. As the call stack unwinds and the function invocations return their values, the result is equivalent to: 2 * 2 * 2 * 1 = 8.

This implementation of Math.pow using recursion is a great way to illustrate the power of recursion by breaking down problems into smaller sub-problems, solving them recursively, and combining the results to obtain the final solution.

The Pros and Cons of Using Recursion

Pros of Using Recursion

  • Optimal Technique: For problems that involve manipulating or iterating through dynamic data structures—such as traversing through a tree or linked list—or while designing solutions that involve sorting or using a divide-and-conquer strategy, recursion naturally lends itself to elegant implementations in these scenarios.
  • Brevity: Recursion can often require fewer lines of code compared to their equivalent iterative solutions, which can make the codebase less verbose and cleaner.

Cons of Using Recursion

  • Performance Overhead: Recursion can be less memory-efficient than iterative solutions due to the overhead of multiple function calls. Each recursive call adds a new frame to the call stack, which can lead to excessive memory usage and a higher space complexity.
  • Risk of Stack Overflow: Anyone first learning about recursion has probably caused a stack overflow. If the recursion depth becomes too deep, it can lead to a stack overflow error, especially in languages with limited stack size. This happens when there are too many nested function calls before reaching the base case. While tail call optimization —where the recursive case is in the tail position and therefore could optimized to not grow the call stack—few JavaScript engines have implemented support for this ECMAScript 6 feature.
  • Debugging Difficulty: Recursive functions can be harder to debug and trace, especially if the base case is not correctly defined, leading to infinite recursion.

When to Use Recursion

Recursion is particularly useful when dealing with problems that have a natural recursive structure, such as:

  • Tree Traversal: Traversing hierarchical data structures like binary trees or graphs is more intuitive with recursion.
  • Divide and Conquer Algorithms: Algorithms like QuickSort and MergeSort benefit from recursion as they divide the problem into smaller subproblems.
  • Dynamic Programming: Some dynamic programming problems, such as calculating Fibonacci numbers, can be solved using recursion (though they may require memoization to optimize performance).

Conclusion

Recursion is a powerful tool in a programmer’s toolkit that allows for elegant and concise solutions to complex problems. However, it’s essential to understand when and how to use recursion effectively, considering both its advantages and potential pitfalls. By carefully structuring recursive functions and being mindful of base cases and stack depth, you can harness the full potential of recursion in your software projects.

If you enjoyed this article, check out How to Build a Hash Table in JavaScript.

Understanding Imperative vs. Declarative Programming in JavaScript

Photo by Markus Spiske on Unsplash

In the world of software engineering, understanding different programming paradigms is crucial for writing efficient and maintainable code. One of the most fundamental paradigm decisions to make is the choice between using imperative versus declarative programming. While both approaches can achieve the same outcomes, they do so in fundamentally different ways. We’ll explore the differences between these two patterns, with a focus on JavaScript, and provide examples to illustrate the pros and cons of each.

Imperative vs. Declarative: A Real World Example

Understanding the benefits and drawbacks of these programming concepts is best achieved through hands-on experience. Imagine the challenges of debugging complex, imperatively written code, or the frustration of navigating over-engineered, overly abstract solutions. While these experiences can be invaluable, a real-world analogy can provide a helpful starting point for understanding the differences between imperative and declarative programming.

The first analogy I heard to describe the imperative/declarative relationship was using an automobile’s air conditioner control panel, so let’s explore that in depth.

Imperative Design of an Automobile A/C Control Panel

1970 Chevrolet A/C Control Panel | Source: ChevyHardcore.com
  • Description: In the past, some cars’ A/C controls used imperative design, where the user set a fan level, selected a vent, and decided a heating/cooling level.
  • Usage: Using this system isn’t too complicated, but it requires an understanding of how all three settings work and how different combinations of settings translate to getting the car to the desired temperature. Not only that, but if the weather or conditions change, the user needs to adjust the settings according. If the weather gets colder or hotter, or if the driver takes a weekend trip out of town, those settings might not be appropriate. Heating the car while on a trip to the desert or cooling the car in the cold mornings don’t make much sense.
  • In other words: The user tells the car how to cool or heat the vehicle.

Declarative Design of an Automobile A/C Control Panel

A Tesla Model 3 Control Panel | Source: Motor Trend
  • Description: Modern cars, like the Tesla Model 3, have more declarative temperature controls. While the user may dive in and adjust the A/C settings more granularly, the main control is a just a left arrow, a right arrow, and the temperature display.
  • Usage: By providing controls to adjust the temperature, the user gets to focus on the desired output rather than the underlying mechanics. The user sets the cabin temperature and the car’s sensors and controllers will adjust the underlying settings to maintain the desired output. The user only needs to be concerned about concepts they understand, like comfortable temperatures, and can allow the car to be concerned with vents, fans, and HVAC.
  • In other words: The user tells the car what temperature they want.

What is Imperative Programming?

As discussed above in the analogy, imperative programming is a paradigm that focuses on how to achieve a particular task. It involves explicitly giving the runtime a sequence of commands or steps to follow in order to reach the desired outcome. In imperative programming, you often define the control flow and manage the state of your program as you go.

What is Declarative Programming?

Declarative programming, on the other hand, focuses on what you want to achieve rather than the intricate details of how to achieve it. In this paradigm, you describe the desired outcome, and the underlying system takes care of the rest. The control flow and state management — the parts of the algorithm that can be made generic and reused elsewhere—are often abstracted away from the algorithm at hand.

An Example of Imperative Programming in JavaScript

Let’s look at a classic example, one that many beginning programmers learn in their early software journeys. Say we want to sum all the numbers in an array. An imperative approach in JavaScript would look like the following:

An example of imperative code written in JavaScript

In the example above, we explicitly define every step of the algorithm:

  1. Initialize a sum variable
  2. Loop through each number in the array
  3. Add each number to the sum

An Example of Declarative Programming in JavaScript

Let’s look at a declarative approach to achieve the same desired output. Using the same example of summing numbers in an array, a declarative approach in JavaScript might use the reduce method on the array prototype:

An example of declarative code written in JavaScript

Here, instead of describing the steps to achieve the sum, we declare that we want to reduce the array to a single value by summing its elements. The reduce method abstracts away the loop and state management.

Pros of Imperative Programming

  • Control: You have precise control over the flow of your program, which can be useful in complex scenarios where you need to manage the state closely.
  • Performance: Imperative code can sometimes be optimized for performance, as you can fine-tune every step of the process.

Cons of Imperative Programming

  • Verbosity: Because you must define each step, imperative code can very quickly become verbose, more difficult to read, and even more difficult to code review. These difficulties compound as complexity increases.
  • Error-Prone: Managing the state manually can lead to bugs, particularly in complicated programs or when operating in lower-level programming languages.
  • Testing Difficulty: Writing unit tests can sometimes become, by definition, impossible because concerns are intermixed.

Pros of Declarative Programming

  • Simplicity: Declarative code is often more concise, easier to understand, and easier to read, as it abstracts away the underlying mechanics.
  • Maintainability: Because you’re focusing on what you want to achieve, the code is typically easier to maintain and less prone to bugs.
  • Reviewability: Declarative code can be more readable, especially for those who are familiar with the abstractions used. This can make it much easier for code reviews.
  • Testability: Writing declarative code often involves separating concerns. This allows for individual features to be isolated and tested easily.

Cons of Declarative Programming

  • Less Control: You have less control over how the task is executed, which can be a drawback if you need fine-tuned performance optimizations.
  • Over-Abstraction: The abstractions provided by declarative methods might introduce overhead or may not be suitable for all scenarios, particularly when performance is critical.

Conclusion

Choosing between imperative and declarative programming is not a simple choice and often involves consideration. Imperative code can give you a lot of control but often at the expense of simplicity, abstracted code that easy to read and maintain. When you need precise control or performance is an primary focus, an imperative approach might make sense. Most other times it probably makes the most sense to use a declarative approach that can lead to cleaner code. With the advent of bundlers, minification, and other optimization tools, small performance improvements become less impactful. As developers, it’s beneficial to be versatile and comfortable with both paradigms, using each where it best fits the problem at hand.

The Difference Between var, let, and const in JavaScript

Variable declaration keywords in JavaScript can seem like the Spider-Man meme.
TL;DR
  • JavaScript has a unique history which has contributed to its confusing features and structure.
  • When considering when to use var, let, or const, you must take into consideration scope, hoisting, redeclaration, and other environmental factors.
  • I prefer to use const for constant values and let for everything else.

Programmers of All Backgrounds Find JavaScript Confusing

Photo by 愚木混株 cdd20 on Unsplash

Without any prior knowledge of JavaScript, doing something as simple as declaring variables can be confusing. Or at least that’s what I found out when I was doing some internal consulting for another department of my old company. I was working with a seasoned pro, someone whose email signature read “Principal Consultant” and who was responsible for architecting entire, full-stack, standalone solutions for external clients that were required to seamlessly integrate with our existing products.

We would have occasional calls to discuss aspects of the project, and we’d often go back and forth via email. Then one day, I popped open my email client and saw an email from him. I liked to tackle his questions first thing in the morning because he lived on the East Coast, and I wanted to make sure I wasn’t blocking him from getting his work done. I read his email and eventually got to a section that read, “What’s the difference between let, const, and var?” I was initially taken aback a bit because such an elementary question to be asked by an engineer with probably twice the experience I had was shocking.

Then I realized this actually makes a lot of sense. JavaScript is confusing, and to have three different ways to declare variables can seem excessive (and it probably is). This pattern was only recently mainstream in the last 5 or so years with ES6, and for someone who hasn’t actively developed in JavaScript recently, the changes from ES6 would make JavaScript seem like an entirely different language from the versions that preceded it. JavaScript has a complicated history, so to understand “why” things are done the way they are, it would be helpful to understand how we got here.

A Brief History of JavaScript

Photo by Natalia Yakovleva on Unsplash

The early web connected people in a way that was only possible in sci-fi films, previously. With that said, it was comprised of slow-loading, static pages that would be unrecognizable today. In 1993, the Mosaic web browser was created, and it allowed users to view web pages with their photos inline with the text (as opposed to in another window).

The lead developers for Mosaic founded Netscape, which introduced the incredibly popular Netscape Navigator. They started working on adding support for a scripting language, which they named JavaScript to ride the coattails of the hot programming language of the time: Java.

Microsoft entered the scene and introduced the Internet Explorer web browser in 1995 and effectively started the “browser wars.” Both web browsers began to support their own scripting languages to provide a richer, more dynamic web browsing experience to the end-users.

Having two main browsers with two separate scripting languages meant that web pages would often only fully function in one browser or the other. This fragmentation lead to the ECMAScript standardization in 1997. With the explosive growth of the internet, ECMAScript (i.e. JavaScript) became the defacto browser language and grew to incredible popularity.

Spotlight Because of its complicated history and its ongoing evolution, JavaScript remains one of the more popular but confusing programming languages to learn.

Being commissioned with being a flexible scripting language while also being born in the shadows of Java made JavaScript a uniquely confusing language. JavaScript is weakly and dynamically typed but you can use the TypeScript superset of JavaScript to add strict typing. You can easily use both the Object-Oriented Programming (OOP) and Functional Programming paradigms in the same application. Because of its complicated history and its ongoing evolution, JavaScript remains one of the more popular but confusing programming languages to learn.

The var keyword

The var keyword is the oldest of the three keywords, and thus, it can be considered a little outdated. It has some odd behavior that can produce bugs without the proper knowledge or development environment configuration.

Scope

A variable declared using the var keyword is function scoped, unless declared outside of a function, then it is globally scoped. Take a look at the illustration below to understand function scoping.

var declarations are scoped to their immediate containing function

The var variable above is scoped to the foo function, and therefore, it is not “visible” to the global scope around it.

Hoisting

var declarations are hoisted and initially undefined before eventually being assigned. The JavaScript interpreter will hoist the declarations of function, variables, and classes and initialize them as undefined (with a few exceptions— keep reading). Thus, we can run the following code below without throwing an exception.

var declarations are hoisted and initialized to undefined

This might be a little confusing, so let’s explain what the JavaScript interpreter is actually doing. Before executing your JavaScript code, the interpreter will scan through and create a mapping of your declarations to optimize the code execution. For all of these declarations, the interpreter doesn’t assign the proper values because this would require executing code. Instead, it creates the mapping with all of these declarations assigned to undefined (again, with a few exceptions). Let’s illustrate this concept in code:

var declarations hoisting can be visualized as undefined, initially

Declaration

The var declaration can be re-declared. This is a subtle but powerfully dangerous concept that should not be overlooked because this feature allows you to introduce naming collisions into your code. Take a look at the example below:

An example of a naming collision using the var keyword

This is a trivial example, but you can imagine how easy it would be to accidentally redeclare a variable in a much larger codebase. Modern development environments will allow you to configure a “linter” to warn you when you may have accidentally reassigned an existing variable.

The let keyword

The keyword let was introduced in ES6, and as this latest ECMAScript standard became widely adopted, let started to overtake var as the go-to keyword to declare variables. There are some main differences that make let a little less permissive, and therefore “safer”, than var.

Scope

let is block-scoped, which is to say, it is scoped to its nearest containing block. So instead of only being scoped to the containing function block like var declarations, let declarations are scoped to the first containing block of all varieties. A block statement in JavaScript is any code in between a valid pair of “curly braces” (i.e. { and }). So, this includes if statements, for and while loops, function declarations, and even a standalone set of curly braces among other use cases. Let’s illustrate what I’m talking about here:

let declarations are block-scoped

Hoisting

While all declarations are hoisted, let declarations behave a little differently than the hoisting described previously for the var keyword. Even though let declarations are hoisted, they are not initialized to undefined like hoisted var declarations are. This means that you can’t reference a variable that is declared using the let keyword before it is initialized.

let declarations are hoisted but not initialized to undefined

This scenario illustrates a quirk that is referred to as the “Temporal Dead Zone (TDZ).” This is a temporal issue because it has to do with timing. Since the variable is not initialized until its first assignment during runtime, an error will be thrown if you try to reference it prematurely.

Declaration

Another way the let keyword is less permissive than var is that it can’t be redeclared. Redeclaring in general is a bit of an odd feature of JavaScript, and designing it out of the let keyword was a major win. Here’s an example of what I’m talking about.

Redeclarations of let variables are not allowed

To be clear, redeclaration and reassignment are two different things. You can definitely reassign let variables as you normally would expect. They wouldn’t be very good variables if they couldn’t vary.

You can still reassign let variables

The const keyword

The const keyword is yet another way to declare variables. As the name would imply, const declarations can be effectively referred to as “constants.” Let’s break down their behavior.

Scope

Much like the let keyword, const declarations are block-scoped.

Hoisting

Hoisting for the const keyword behaves exactly the same way as the let keyword. It is hoisted but uninitialized, and therefore, it will experience the same Temporal Dead Zone issues.

Declaration

You can’t redeclare a const declaration once you’ve already declared it. Again, this is the exact same behavior as with let declarations. However, because lets and consts are block-scoped, it may sometimes seem like they are being redeclared when they actually aren’t. Take a look at this example:

Block scoping can create the illusion of redeclaration

You’ll notice that we declare and assign the foo constant twice, but the execution of our code will not throw an exception. Again, this is because of the block scoping nature of const declarations.

Assignment

The main feature of the const keyword is that it can’t be reassigned. Therefore, you must immediately assign a value to the constant, otherwise, that constant will remain undefined. One notable “loophole” can be seen below:

A “loophole” to change the value of a constant

Even though foo is a constant, the code above does not generate an exception. Can you tell what’s going on here? Take a second to think about it.

Although it appears that we’re violating the primary feature of the const keyword, strictly speaking, we aren’t actually reassigning the foo constant. This is because we are using the Object data structure. So we initialize foo to an Object instance, and at every step of the way, foo is always referencing that same Object instance. We are simply adding another property to that object instead of reassigning foo.

When to Use Them

You should use whatever you feel comfortable with, but I like to only be as permissive as is required. If your value will never need to be reassigned, use const, otherwise, use a let. I never use vars anymore because they are too permissive. If I ever need to reference a variable outside of its scope, I simply move the variable declaration to a higher, common scope. I’ve also never had a reason to take advantage of var’s lack of a Temporal Dead Zone, and in fact, I see that attribute as more of a bug and not a feature.

Conclusion

Even experienced developers can find JavaScript confusing at times. Its unusual history makes it one of the most popular languages today, but also one of the most difficult to master. Developing a thorough understanding of var, let, and const is an important step to building a strong JavaScript foundation.