A Quick Intro to Recursion in Javascript

As a full-stack developer, recursion is an essential concept to understand. Many programming problems can be solved elegantly using recursion. In this guide, we‘ll dive into what recursion is, how it works in Javascript, look at some examples, and discuss best practices for writing recursive functions.

What is Recursion?

Recursion is a programming technique where a function calls itself repeatedly until a certain condition is met. It‘s a way to break down complex problems into smaller sub-problems that are more manageable to solve.

The key idea behind recursion is that you can define a problem in terms of itself. A recursive function will continue to call itself and repeat its behavior until some condition is met to return a result. All recursive functions share a common structure made up of two parts: the base case and the recursive case.

Base Case vs Recursive Case

Every recursive function must have a base case – a condition where the function will stop calling itself and start returning a value back up the call stack. The base case is typically a problem that is small enough to solve directly.

The recursive case is where the recursion happens. The recursive function calls itself with a modified version of the original problem. With each recursive call, the input gets smaller and smaller, until it eventually reaches the base case.

If a recursive function is missing a base case or the base case is written incorrectly, you‘ll get infinite recursion which leads to a stack overflow error. More on this later.

Recursion vs Iteration

Many problems that can be solved recursively can also be solved iteratively using for and while loops. In general, if you can solve a problem iteratively, that‘s usually the best approach in terms of performance. Recursive functions tend to be less efficient in terms of memory and processing time.

However, recursion really shines when applied to problems that have a naturally recursive structure like trees, graphs, and other complex data structures. Recursion can help make the code more readable and reduce its complexity compared to an iterative approach.

The Javascript Call Stack

To understand how recursion works, it‘s important to be familiar with the call stack. In Javascript, the call stack is a data structure that stores information about the active functions that have been called. When a function is invoked, it‘s added (pushed) to the top of the call stack. When the function finishes executing, it‘s removed (popped) from the stack.

Recursive functions use the call stack to keep track of the function calls. With each recursive call, a new stack frame is added to the call stack, holding the arguments passed in and the current state of the function. This process continues until the base case is reached. Then the stack frames start to unwind and return values back up the call stack.

Stack Overflow

A common pitfall with recursive functions is stack overflow. If a recursive function calls itself too many times (i.e. infinite recursion), the call stack will grow larger and larger with each call. Since the call stack has a fixed amount of memory, eventually it will run out of space and "overflow," leading to a stack overflow error which crashes the program.

To avoid stack overflow, always make sure that your recursive function has a well-defined base case and that each recursive call is progressively getting closer to that base case.

Examples of Recursion

Now that we understand the fundamentals, let‘s look at some classic examples of recursion in Javascript.

Factorial

The factorial of a number n is the product of all positive integers less than or equal to n. We can calculate factorials using the following recursive function:

function factorial(n) {
  if (n === 0) { // base case
    return 1;
  } else {
    return n * factorial(n - 1); // recursive case 
  }
}

console.log(factorial(5)); // 120

The base case is when n is 0, in which case we return 1 since 0! = 1 by definition.
The recursive case multiplies n by the factorial of n – 1.
So to find 5!, we recursively calculate 5 4!, 4 3!, 3 2!, 2 1!, 1 * 0!.

Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding numbers, usually starting with 0 and 1. It begins 0, 1, 1, 2, 3, 5, 8, 13, 21…

We can generate Fibonacci numbers using this recursive function:

function fibonacci(n) {
  if (n <= 1) { // base case
    return n;
  } else {
    // recursive case
    return fibonacci(n - 1) + fibonacci(n - 2); 
  }
}

console.log(fibonacci(8)); // 21

The base cases are n = 0 and n = 1 which return n.
The recursive case states that the nth Fibonacci number is equal to the sum of the previous two Fibonacci numbers, recursively calling itself to calculate those values.

Traversing Nested Objects

Recursion can be useful for searching through nested objects of arbitrary depth. Here‘s an example:

const userInfo = {
  name: "John",
  address: {
    street: "123 Main St",
    city: "Anytown",
    state: {
      code: "NY",
      fullName: "New York"
    }, 
    zip: 12345
  },
  hobbies: ["reading", "hiking", "coding"]
};

function getValueByKey(obj, key) {
  for (let prop in obj) {
    if (prop === key) {
      return obj[prop]; // base case      
    } 
    if (typeof obj[prop] === "object") {
      // recursive case
      const value = getValueByKey(obj[prop], key);
      if (value) {
        return value;
      }
    }
  }
}

console.log(getValueByKey(userInfo, "state")); 
// { code: "NY", fullName: "New York" }

This function takes an object and a key and searches for that key in the object. If it finds the key, it returns the corresponding value (base case). If not, it recursively searches through nested objects (recursive case) until it finds the key or reaches the end.

Tips for Writing Recursive Functions

Here are some tips to keep in mind when writing recursive functions:

1. Break the problem down into smaller sub-problems that can be solved recursively.
2. Figure out the base case(s) – the simplest possible case that can be solved without further recursion.
3. Make sure each recursive call is working towards the base case, getting smaller with each call.
4. Don‘t forget to return values in the base and recursive cases to pass the value back up the call stack.
5. Test with different input to ensure the function handles all cases.
6. If the recursive version is getting too complex, see if you can rewrite it iteratively instead.

When to Use Recursion

Recursion is a powerful technique, but it‘s not always the best tool for the job. You should consider using recursion when:

• The problem can be broken down into smaller sub-problems
• The problem is complex and an iterative solution would be messy
• You‘re working with recursive data structures like trees and graphs
• You need a quick solution and performance is not critical

But you should avoid recursion if:

• The problem is simple and can be easily solved with a loop
• Recursion would lead to deeply nested calls and potential stack overflow
• Memory and processing time are limited

Real-World Uses of Recursion

Recursion has many practical applications in software development. Some common use cases include:

• Traversing and searching data structures like binary trees, graphs, and linked lists
• Implementing divide and conquer algorithms like merge sort and quick sort
• Exploring all possibilities in backtracking algorithms like sudoku solvers
• Processing hierarchical data formats like JSON and XML
• Rendering fractal patterns and other self-similar graphics

Understanding recursion is an important step to becoming a better programmer. Knowing when and how to apply it can help you write more concise, manageable code.

Conclusion

We covered a lot of ground in this guide to recursion in Javascript. To recap, recursion is when a function calls itself until it reaches a base case. Recursive functions can make complex problems more manageable, but they do come with some downsides like potential stack overflow.

When deciding between recursion and iteration, consider the complexity of the problem and whether a recursive solution would be cleaner than an iterative one. And if you do use recursion, make sure to define a base case to avoid infinite recursion.

The best way to get comfortable with recursion is through practice. Start with classic examples like calculating factorials and Fibonacci numbers, then move on to more complex problems like searching and sorting recursive data structures.

I hope this guide helped demystify the concept of recursion and gave you the knowledge you need to start applying it in your own Javascript projects. Recursive programming takes time to wrap your head around, but once it clicks, it can be a very satisfying way to solve coding challenges.

Happy recursing!