Hva er rekursjon?

Question

Hva er rekursjon?

Accepted Answer

**Rekursjon** er når en funksjon kaller seg selv for å løse en mindre versjon av samme problem. Hver rekursjon trenger en **base case** som stopper den og en **recursive case** som beveger seg mot basen.

## Idéen

Del et problem inn i mindre identiske delproblemer. Hvert kall pusher en frame på **call stack**; returns popper dem av.

## Eksempel

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

## Sporing

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

## Kompleksitet

Her **O(n)** tid og **O(n)** stack-plass (én frame per kall).

## Fallgruver

- **Manglende base case** -> uendelig rekursjon -> stack overflow.
- Dyp rekursjon kan oppbruke stacken; noen språk mangler tail-call optimalisering.
- Omberegning av overlappende delproblemer kan bli eksponentiell tid (fix med memoization).

## Hvorfor det er viktig

Rekursjon uttrykker naturlig selvslikt problemer — trær, grafer, divide and conquer — langt renere enn løkker.

Det er den mentale modellen bak merge sort, backtracking og dynamic programming.

Å forstå call stack gjør deg også bedre til å debugge og resonnere om minne.