What is recursion?

Question

What is recursion?

Accepted Answer

**Recursion** is when a function calls itself to solve a smaller version of the same problem. Every recursion needs a **base case** that stops it and a **recursive case** that moves toward the base.

## The idea

Break a problem into smaller identical subproblems. Each call pushes a frame onto the **call stack**; returns pop them off.

## Example

```python
def factorial(n):
    if n <= 1:            # base case: stop recursing
        return 1
    return n * factorial(n - 1)   # recursive case: smaller problem

factorial(4)             # 4 * 3 * 2 * 1 -> 24
```

## Trace

```text
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24
```

## Complexity

Here **O(n)** time and **O(n)** stack space (one frame per call).

## Pitfalls

- **Missing base case** -> infinite recursion -> stack overflow.
- Deep recursion can exhaust the stack; some languages lack tail-call optimization.
- Recomputing overlapping subproblems can blow up to exponential time (fix with memoization).

## Why it matters

Recursion expresses naturally self-similar problems — trees, graphs, divide and conquer — far more cleanly than loops.

It is the mental model behind merge sort, backtracking, and dynamic programming.

Understanding the call stack also makes you better at debugging and reasoning about memory.