# Recursion — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/recursion

> A function that solves a problem by calling itself on a smaller input.

## Base case + recursive case

Every recursion needs (1) a **base case** that returns without recursing, and (2) a **recursive case** that makes progress toward the base. Miss the base case and you get a stack overflow.

## The call stack unwinds

`factorial(3)` waits for `factorial(2)` which waits for `factorial(1)`. Then results multiply back up.

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

# factorial(3)
# = 3 * factorial(2)
# = 3 * (2 * factorial(1))
# = 3 * (2 * 1) = 6
```

## Russian dolls

Open a doll to find a smaller one, until the tiny solid one (base case). Then close them back up in order.

## Recursion → iteration

Any recursion can be rewritten with an explicit stack. Tail recursion and repeated subproblems (Fibonacci) are signals to memoise or go bottom-up.