Kaj je rekurzija?

Question

Kaj je rekurzija?

Accepted Answer

**Rekurzija** je, ko funkcija kliče sama sebe, da reši manjšo različico istega problema. Vsaka rekurzija potrebuje **bazni primer**, ki jo ustavi, in **rekurzivni primer**, ki se giblje proti bazni točki.

## Ideja

Razdeli problem na manjše identične podprobleme. Vsak klic potisne okvir na **call stack**; povratne vrednosti jih snemajo.

## Primer

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

## Sled

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

## Kompleksnost

Tu je **O(n)** čas in **O(n)** prostora stack (en okvir na klic).

## Pasti

- **Manjkajoči bazni primer** -> neskončna rekurzija -> stack overflow.
- Globoka rekurzija lahko porabi stack; nekatere jezike nimajo tail-call optimizacije.
- Ponovno računanje prekrivajočih se podproblemov lahko eksplodira v eksponentni čas (popraviti z memoizacijo).

## Zakaj je to važno

Rekurzija naravno izrazi samopodobne probleme — drevesa, grafe, deli in vladaj — veliko čisteje kot zanke.

Je miselni model za merge sort, backtracking in dinamičko programiranje.

Razumevanje call stack te tudi naredi boljšega pri debugiranju in razmišljanju o pomnilniku.