Introduction

As you know, I love blog-driven development.

I got a little bit confused about recursion when building a Linked List (data structure).

I ended up writing this piece for myself.

Enjoy the read.

What's recursion?

Let's use the Inception analogy! Remember that movie scene where they dream within a dream and then... within another dream?

That's somewhat like recursion. In programming, it means a function that says, "I'm going to solve a part of this problem and let another 'mini-me' function handle the rest!" So, it calls itself until the problem is completely solved.

History of recursion

Back in the day, nature was showing off recursion with stuff like snowflakes and branching trees.

Fast forward, Fibonacci used recursion in a number sequence.

Fast forward even more, coders love recursion because it's like a magic trick for tough problems.

In short, recursion's been everywhere, from nature's patterns to today's code!

Why does it exist?

1. Problem Splitting: Sometimes, staring at a big problem is hard. But if you can make it into a "mini-version" of itself, then the problem becomes easier.

2. Elegance: For certain problems, recursion offers an elegant solution.

3. Data Structures: Structures like trees and graphs have a recursive nature. Imagine going through a family tree: "Who's the parent of the parent of the parent...?"

Basics

1. Base Case: This is your escape hatch. Without it, you're stuck in the recursive dream forever (or at least until the system crashes). It defines when to stop.

2. Recursive Case: The function is called here, but with a smaller or simpler piece of the problem.

Pros

• Clean Code: For some problems, recursion provides a neat solution without many lines of code.

• Tree & Graph Structures: Walking through trees (like the Document Object Model in web dev) is often naturally recursive.

• Divide & Conquer: Helps to break down complex problems into smaller, more manageable ones.

Cons

• Efficiency: Each function call consumes memory. A loop might handle the same task more efficiently.

• Stack Overflow: Too much recursion can crash your program because it uses up all the space reserved for function calls.

• Complexity: For newcomers, recursion can sometimes be a bit harder to wrap the head around compared to loops.

When to consider?

Imagine you're building software and face problems like navigating a deeply nested menu, searching through hierarchical data, or implementing certain algorithms.

If you notice that the task at hand can be broken down into simpler, repetitive steps, then consider recursion.

Inner workings

Every recursive call gets added to the Stack. The pattern it follows is "last in, first out". So the last function call will be the one first completing.

The key takeaway here is that every recursive call remains "paused" until all of the deeper recursive calls complete.

Each function call gets its own space in memory (often visualized as a stack frame). These stack frames hold function parameters, local variables, and the return address.

Let's say we have a countDown function where the base gets hit when the number becomes zero.

This is roughly how it would look like running till it hits the base case:

Stack:
countDown(3) --> still running (paused)
countDown(2) --> still running (paused)
countDown(1) --> still running (paused)
countDown(0) --> completed

Once the last function has been popped off the stack (the one that hit the base case), the next one runs. It recursively moves up and completes each function.

Realistic Examples

Directory traversal

Let's say you're working on a file management system, something like Dropbox or Google Drive. Users can have folders, and within those folders, they can have more folders and files.

/**
 * Recursively counts the total number of files in a directory and its subdirectories.
 * @param {Directory} directory - The directory to start the count from.
 * @returns {number} - Total number of files.
 */
function countFiles(directory) {
    // Count the files in the current directory
    let count = directory.files.length;

    // Recursively count files in each subdirectory
    for (let subdirectory of directory.subdirectories) {
        count += countFiles(subdirectory);
    }

    return count;
}

Comments system

Imagine you're developing a discussion platform similar to Reddit.

Users can leave comments, and other users can reply to those comments. This can go several layers deep (a comment on a comment on a comment, and so on). Now, you need a function that can print all comments and their replies in a structured way.

/**
 * Recursively prints a comment and its replies.
 * @param {Comment} comment - The comment to start printing from.
 * @param {string} indent - Current level of indentation for visual structure.
 */
function printComment(comment, indent = '') {
    // Print the current comment with the current level of indentation
    console.log(indent + comment.text);

    // Recursively print replies to this comment, increasing the indentation
    for (let reply of comment.replies) {
        printComment(reply, indent + '---');
    }
}

Common Mistakes

Forgetting the base case

The base case is essential in recursion. Without it, your recursive function will run indefinitely, leading to a stack overflow. It's the condition under which the function stops calling itself.

// Bad example
function countDown(number) {
    console.log(number);
    countDown(number - 1);
}

// Good example
function countDown(number) {
    if (number <= 0) {
        console.log("Done!");
        return;
    }
    console.log(number);
    countDown(number - 1);
}

Not Modifying Input for the Recursive Call

Each recursive call should bring you one step closer to the base case. If you don't modify the inputs in a way that moves you towards the base case, you'll end up with infinite recursion.

// Bad example
function factorial(n) {
    if (n === 0) return 1;
    return n * factorial(n);
}

// Good example
function factorial(n) {
    if (n === 0) return 1;
    return n * factorial(n - 1);
}

Misunderstanding the Recursive Stack

It's important to remember that each recursive call gets its own execution context. Local variables aren't shared between calls.

// Bad example: Thinking that 'sum' will aggregate across recursive calls
function sumToN(n) {
    let sum = 0;
    if (n <= 1) return n;
    sum += n + sumToN(n - 1);
    return sum;
}

// Good example
function sumToN(n) {
    if (n <= 1) return n;
    return n + sumToN(n - 1);
}

Ignoring the Return Value

Recursive functions often rely on return values of their recursive calls.

Ignoring or forgetting to use these can lead to incorrect results.

// Bad example: Ignoring the return value
function reverseString(str) {
    if (str === "") return "";
    const lastChar = str[str.length - 1];
    reverseString(str.substring(0, str.length - 1));
    return lastChar;
}

// Good example
function reverseString(str) {
    if (str === "") return "";
    const lastChar = str[str.length - 1];
    // Make sure to return the recursive call
    return lastChar + reverseString(str.substring(0, str.length - 1));
}

This however is necessary if you want something returned from the function.

Conclusion

Recursion is beautiful when used right.

The tricky part lies in understanding how the inner workings work.

I hope you enjoyed this.