Hvad er rekursion?

Question

Hvad er rekursion?

Accepted Answer

**Rekursion** er når en funktion kalder sig selv for at løse en mindre udgave af samme problem. Hver rekursion har brug for et **basetilfælde (base case)**, der stopper det, og et **rekursivt tilfælde (recursive case)**, der bevæger sig mod basistilfeldet.

## Ideen

Del et problem op i mindre identiske delproblemer. Hver kald skubber en ramme på **call stack**-en; returneringer pop'er dem af.

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

## Spor

```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-plads (en ramme per kald).

## Faldgruber

- **Manglende basetilfælde** -> uendelig rekursion -> stack overflow.
- Dyb rekursion kan udtømme stacken; nogle sprog mangler tail-call optimization.
- Genberegning af overlappende delproblemer kan blive eksponentiel tid (fix med memoization).

## Hvorfor det betyder noget

Rekursion udtrykker naturligt selv-lignende problemer — træer, grafer, del og erobre — meget renere end løkker.

Det er den mentale model bag merge sort, backtracking og dynamisk programmering.

At forstå call stack'en gør dig også bedre til fejlfinding og ræsonnering om hukommelse.