Vad är rekursion?

Question

Vad är rekursion?

IT Interview Practice · Accepted Answer

**Rekursion** är när en funktion anropar sig själv för att lösa en mindre version av samma problem. Varje rekursion behöver ett **basfall** som stoppar den och ett **rekursivt fall** som flyttar sig mot basen.

## Idén

Dela ett problem i mindre identiska delproblem. Varje anrop pushar en frame på **call stack**; returer poppar dem.

## Exempel

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

## Spårning

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

## Komplexitet

Här är det **O(n)** tid och **O(n)** stack-utrymme (en frame per anrop).

## Fallgropar

- **Saknat basfall** -> oändlig rekursion -> stack overflow.
- Djup rekursion kan uttömma stacken; vissa språk saknar tail-call optimering.
- Omberäkning av överlappande delproblem kan explodera till exponentiell tid (åtgärda med memoization).

## Varför det är viktigt

Rekursion uttrycker naturligt självliknande problem — träd, grafer, dela och härska — mycket renare än loopar.

Det är den mentala modellen bakom merge sort, backtracking och dynamisk programmering.

Att förstå call stack gör dig också bättre på att felsöka och resonera om minne.

Idén

Exempel

Spårning

Komplexitet

Fallgropar

Varför det är viktigt

Relaterade frågor