What is recursion, and when should you use it?
A function that calls itself, solving a problem by reducing it to a smaller version of the same problem until it reaches a case simple enough to answer directly.
The two required parts. A base case, which returns without recursing — and a recursive case, which must move towards the base case. Omitting the base case, or failing to make progress towards it, produces infinite recursion and a stack overflow, which is the characteristic failure.
Why it uses the stack. Each call allocates a stack frame holding its local state, and frames accumulate until the base case unwinds them. This is the fundamental constraint: recursion depth is limited by stack size, typically thousands to tens of thousands of frames. A loop has no such limit.
Where recursion is genuinely the right tool:
Recursively defined structures — trees, file systems, nested JSON, the DOM, organisation charts. Traversing a tree iteratively requires managing an explicit stack, which is simply recursion written out by hand and usually less clear.
Divide and conquer algorithms — merge sort, quicksort, binary search.
Backtracking — permutations, puzzle solving, pathfinding with undo.
Parsing, where grammars are themselves recursive.
Where it is the wrong tool: simple iteration over a sequence, where a loop is clearer and cheaper; very deep structures, where the stack will not hold; and performance-critical code, where call overhead matters.
Tail recursion, where the recursive call is the last operation, can be optimised into a loop by the compiler — but many popular languages do not guarantee this, so a tail-recursive function in those languages still overflows.
The practical failure mode. Naive recursion recomputes the same subproblems exponentially — the classic being a Fibonacci implementation that is unusable beyond small inputs. The fix is memoisation or converting to a bottom-up iterative form, which is the core idea of dynamic programming.
The honest advice: use it where the data is recursive, and use a loop otherwise. Choosing recursion to appear clever produces code that is harder to read and easier to break.