Recursion in Data Structures Base Case

Base Case and Progress Measure

Recursion solves a problem by calling the same operation on a smaller state. Correctness requires a base case, progress toward it on every branch, and a way to combine returned results.

The base case returns without another recursive call. A progress measure such as remaining length, tree depth, or unvisited nodes must decrease toward that case. Validate input that could violate the measure, including cycles in structures assumed to be trees.

Call Stack and Unwinding

Each call stores parameters, locals, and a return location. Calls descend until a base case, then unwind in reverse order. Trace small input by writing one row per call and a second row per return; this separates downward work from result combination.

Recursive Data Structures

Trees, nested syntax, directory structures, and divide-and-conquer ranges naturally contain smaller instances of the same shape. Graph traversal additionally needs a visited set, or cycles can recurse forever.

Complexity and Conversion to Iteration

Count both the number of calls and maximum active depth. A traversal may be O(n) time but O(h) stack space. For deep or untrusted input, replace implicit recursion with an explicit stack that stores each pending node and any post-child state. Memoization reduces repeated overlapping subproblems but does not repair a missing base case.

Recursive Tree Sum

function sumTree(node) {
        if (node === null) return 0;
        return node.value + sumTree(node.left) + sumTree(node.right);
      }

Cycle-Safe Graph DFS

function visit(graph, start, seen = new Set()) {
        if (seen.has(start)) return;
        seen.add(start);
        for (const next of graph.get(start) ?? []) visit(graph, next, seen);
      }

Before you move on