What is Recursion in Javascript and How to Use it as a Beginner

Imagine you’re standing between two mirrors facing each other. The reflection creates an infinite series of images, each one smaller than the last. This is similar to how recursion works in programming – a function that calls itself to solve a problem by breaking it down into smaller versions of the same problem.

What is Recursion?

Recursion is a programming concept where a function solves a problem by calling itself with a smaller version of the same problem. Each time the function calls itself, it works with a simpler case until it reaches a condition that can be solved directly – known as the base case.

Let’s look at a simple example:

function countDown(number) {
    // Base case: when we reach zero
    if (number === 0) {
        console.log("Done!");
        return;
    }

    // Display the current number
    console.log(number);

    // Recursive case: call the function with a smaller number
    countDown(number - 1);
}

// Try it out
countDown(5);

In this example, we start with the number 5 and count down to zero. Each time the function calls itself, it reduces the number by 1 until it reaches zero (our base case).

The Two Key Parts of Recursion

1. Base Case

Every recursive function needs a stopping point – this is the base case. It’s the simplest version of the problem that we can solve directly. For example, in the factorial problem, our base case is when we reach 1.

2. Recursive Case

This is where we break down our bigger problem into a smaller one. Each time the function calls itself, it should work with a simpler version of the problem. For example, calculating factorial(5) becomes calculating factorial(4), then factorial(3), and so on.

Recursion Examples

Let’s explore some practical examples with recursion :

Example 1: Calculate Factorial

The factorial of a number is a perfect example of recursion in action. For instance, factorial of 5 (written as 5!) equals 5 × 4 × 3 × 2 × 1.

function factorial(n) {
    // Base case: factorial of 0 or 1 is 1
    if (n <= 1) {
        return 1;
    }

    // Recursive case: n! = n × (n-1)!
    return n * factorial(n - 1);
}

// Let's calculate 5!
console.log(factorial(5)); // Output: 120

Let’s break down how this works:

1. factorial(5) = 5 × factorial(4)
2. factorial(4) = 4 × factorial(3)
3. factorial(3) = 3 × factorial(2)
4. factorial(2) = 2 × factorial(1)
5. factorial(1) = 1 (base case)

Example 2: Traversing a Directory Structure

Recursion is particularly useful when working with nested structures. Here’s how we might use recursion to print a directory structure:

function traverseDirectory(directory, level = 0) {
    // Create indentation based on level
    const indent = "  ".repeat(level);

    // Print current directory name
    console.log(`${indent}📁 ${directory.name}`);

    // Base case: no subdirectories
    if (!directory.subdirectories) {
        return;
    }

    // Recursive case: traverse each subdirectory
    directory.subdirectories.forEach(subdir => {
        traverseDirectory(subdir, level + 1);
    });
}

// Example usage
const fileSystem = {
    name: "root",
    subdirectories: [
        {
            name: "documents",
            subdirectories: [
                { name: "work" },
                { name: "personal" }
            ]
        },
        {
            name: "pictures",
            subdirectories: [
                { name: "vacation" }
            ]
        }
    ]
};

traverseDirectory(fileSystem);

Common Pitfalls and How to Avoid Them

1. Missing Base Case

One of the most common mistakes is forgetting to define a proper base case:

// ❌ Incorrect: No base case
function infiniteRecursion(n) {
    return infiniteRecursion(n - 1);
}

// ✅ Correct: With base case
function safeRecursion(n) {
    if (n <= 0) {
        return 0;
    }
    return safeRecursion(n - 1);
}

2. Stack Overflow

When recursion goes too deep, it can cause a stack overflow. Here’s how to prevent it:

// ❌ Potential stack overflow with large numbers
function deepRecursion(n) {
    if (n === 0) return 0;
    return 1 + deepRecursion(n - 1);
}

// ✅ Better: Using tail recursion
function safeDeepRecursion(n, accumulator = 0) {
    if (n === 0) return accumulator;
    return safeDeepRecursion(n - 1, accumulator + 1);
}

Advanced Concepts Of Recursion

Tail Recursion

Tail recursion happens when we make the recursive call our last step. It’s a special way of writing recursive functions that can be more efficient. Think of it like passing the ongoing results forward instead of waiting to combine them on the way back:

// Traditional recursion
function sum(n) {
    if (n <= 1) return n;
    return n + sum(n - 1);
}

// Tail recursive version
function tailSum(n, accumulator = 0) {
    if (n <= 1) return n + accumulator;
    return tailSum(n - 1, accumulator + n);
}

Recursive vs. Iterative Solutions

Sometimes, you can solve the same problem using either recursion or iteration. Here’s a comparison:

// Recursive Fibonacci
function fibRecursive(n) {
    if (n <= 1) return n;
    return fibRecursive(n - 1) + fibRecursive(n - 2);
}

// Iterative Fibonacci
function fibIterative(n) {
    if (n <= 1) return n;
    let prev = 0, current = 1;

    for (let i = 2; i <= n; i++) {
        [prev, current] = [current, prev + current];
    }

    return current;
}

Try It Yourself

Start with these simple problems to practice recursion:

1. Add up all numbers from 1 to n
2. Find the nth Fibonacci number
3. Turn a string backwards
4. Find the GCD of two numbers
5. Search through a sorted list using recursion

Here’s a template to get you started:

function recursiveProblem(input) {
    // 1. Define your base case
    if (/* base condition */) {
        return /* base solution */;
    }

    // 2. Define your recursive case
    return /* recursive call with smaller input */;
}

Conclusion

Recursion is a powerful tool in your programming toolkit. While it might seem challenging at first, with practice and understanding, you’ll find it becomes an intuitive way to solve complex problems. Remember these key points:

1. Always define a clear base case
2. Ensure each recursive call moves toward the base case
3. Consider performance implications
4. Practice with simple examples before tackling complex problems

Keep practicing, and don’t get discouraged if it takes time to grasp. The ability to think recursively is a valuable skill that will serve you well throughout your programming journey.