Recursion Patterns — Tree Walk, Permutations & More

Recursion is a function that calls itself. It's the natural way to process trees, generate combinations, and traverse nested structures. This article covers core recursive patterns, the stack overflow problem, tail-call optimization, and iterative alternatives.

1. The Anatomy of a Recursive Function

Every recursive function has two parts: a base case (stop condition) and a recursive case (call itself with a smaller problem):

Without a base case, you get infinite recursion → stack overflow. Every function call consumes stack memory, and the stack is finite.

2. Deep Flatten — Recursive vs Iterative

3. Fibonacci — Three Ways

4. Tree Traversal

5. Generating All Permutations

6. Generating All Combinations (Powerset)

7. Tail-Call Optimization (TCO)

A recursive call is in tail position if it's the very last thing the function does. JavaScript engines can optimize tail calls to avoid stack growth, but only Safari/JSC currently implements TCO:

8. Trampolining — Manual TCO When the Engine Doesn't Support It

Key Takeaways

• Every recursive function needs a base case — without it, stack overflow.
• Deep recursion is elegant but can overflow the call stack on large/deep inputs.
• Memoization turns exponential recursive algorithms (Fibonacci) into O(n).
• Iterative + stack is the stack-safe alternative when the engine doesn't do TCO.
• Trampolining enables unbounded recursion by returning thunks a trampoline function executes in a loop.

Next: Data #1 — Deep Clone & Deep Compare — structural clone handling circular references and deep equality checking.