Što je rekurzija?

Question

Što je rekurzija?

Accepted Answer

**Rekurzija** je kada funkcija poziva samu sebe kako bi riješila manju verziju istog problema. Svaka rekurzija trebala bi **bazni slučaj** koji je zaustavlja i **rekurzivni slučaj** koji se kreće prema bazi.

## Ideja

Razložite problem na manje identične podprobleme. Svaki poziv gura okvir na **pozivni stog**; povratci ih izvlače.

## Primjer

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

## Praćenje

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

## Složenost

Ovdje **O(n)** vremenske složenosti i **O(n)** prostora stoga (jedan okvir po pozivu).

## Zamke

- **Nedostaje bazni slučaj** -> beskonačna rekurzija -> prelazak stoga.
- Duboka rekurzija može iscrpiti stog; neki jezici nemaju optimizaciju završnog poziva.
- Ponovno računanje preklapajućih podproblema može porasti na eksponencijalno vrijeme (ispravite s memoizacijom).

## Zašto je važno

Rekurzija prirodno izražava sami-slične probleme — stabla, grafove, podijeli pa vladaj — mnogo čišće nego petlje.

To je mentalni model iza sortiranja spajanjem, vraćanja unazad i dinamičkog programiranja.

Razumijevanje pozivnog stoga čini vas boljim i pri otklanjanju greške i pri razmišljanju o memoriji.