Recursion made simple by someone who struggled with it

Recursion confused me for a long time. Not the concept—I understood that a function could call itself. What I couldn't grasp was how to think about it. How do you write a recursive function without tracing the entire call chain in your head?

The answer is: you don't. You write one step and trust the rest.

The Two-Part Structure

Every recursive function has two parts:

1. The base case: when to stop
2. The recursive case: reduce the problem and call yourself

If you get these two right, the recursion works. You don't need to trace the full call stack—the computer does that.

function factorial(n) {
    // Base case: we know the answer
    if (n <= 1) return 1;
    
    // Recursive case: reduce the problem
    return n * factorial(n - 1);
}

The function doesn't need to know what factorial(n - 1) returns. It just needs to know that it returns the right answer, and then combine it with n.

Tree Traversal: Where Recursion Shines

function traverseTree(node) {
    if (!node) return; // Base case: null node
    
    console.log(node.value);
    traverseTree(node.left);  // Trust left subtree
    traverseTree(node.right); // Trust right subtree
}

The iterative version of this requires an explicit stack and 15 more lines. The recursive version is four lines and reads exactly like the definition of a tree traversal.

When Not to Use It

Recursion builds a call stack. Deep recursion on large inputs will overflow the stack. Most languages have a call stack limit of a few thousand frames.

For deeply nested data or large datasets, use iteration with an explicit stack, or look for a tail-recursive approach if your language optimizes it.

The Mindset Shift

Stop trying to simulate the full recursion. Write the base case. Write one recursive step. If those two things are correct, the function is correct.