Recursion

Recursion occurs when a function calls itself to solve a smaller instance of the same problem. Every recursive solution requires:

Base case(s): The smallest input that can be solved directly, without recursion.
Recursive case(s): The problem is reduced toward the base case.

The Call Stack

Each recursive call pushes a new frame onto the call stack containing local variables and the return address. When the base case is reached, frames pop off in reverse order.

Depth limit: Each language/runtime has a maximum stack depth. Exceeding it causes a stack overflow.

Divide and Conquer

A recursive pattern where a problem is:

Divide into smaller subproblems of the same type.
Conquer each subproblem recursively.
Combine the results into the final answer.

Examples: Merge sort, quicksort, binary search, tree traversals.

Tail Recursion

A recursive call is tail recursive when it’s the last operation in the function — the function returns the result of the recursive call directly. Compilers can optimize tail recursion into a loop (reusing the same stack frame), avoiding stack growth.

When to Use Recursion

Problems with a natural recursive structure (trees, graphs, divide-and-conquer).
When iterative solutions are significantly more complex (tree traversals, backtracking).
When readability and mathematical clarity outweigh performance concerns.

When to Avoid Recursion

When stack depth could be large (prefer iteration or tail recursion).
When performance-critical (function call overhead matters).
When the iterative solution is equally clear.