Wat is recursie?

Question

Wat is recursie?

Accepted Answer

**Recursie** is wanneer een functie zichzelf aanroept om een kleinere versie van hetzelfde probleem op te lossen. Elke recursie heeft een **base case** nodig die deze stopt en een **recursive case** die naar de base gaat.

## Het idee

Verdeel een probleem in kleinere identieke subproblemen. Elke aanroep duwt een frame op de **call stack**; returns halen deze eraf.

## Voorbeeld

```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
```

## Complexiteit

Hier **O(n)** tijd en **O(n)** stack ruimte (één frame per aanroep).

## Valkuilen

- **Ontbrekende base case** -> oneindige recursie -> stack overflow.
- Diepe recursie kan de stack uitputten; sommige talen hebben geen tail-call optimalisatie.
- Het opnieuw berekenen van overlappende subproblemen kan tot exponentiële tijd leiden (repareer met memoization).

## Waarom het belangrijk is

Recursie drukt natuurlijk zelfsimilaire problemen uit — bomen, grafieken, divide and conquer — veel schoner dan lussen.

Het is het mentale model achter merge sort, backtracking en dynamic programming.

De call stack begrijpen maakt je ook beter in debuggen en redeneren over geheugen.