Co je rekurze?

Question

Co je rekurze?

Accepted Answer

**Rekurze** je, když si funkce volá sama, aby vyřešila menší verzi stejného problému. Každá rekurze potřebuje **základní případ (base case)**, který ji zastaví, a **rekurzivní případ (recursive case)**, který se pohybuje směrem k základnímu případu.

## Idea

Rozdělte problém na menší identické podproblémy. Každé volání vloží rámec na **zásobník volání (call stack)**; návraty je odstraní.

## Příklad

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

## Trasování

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

## Složitost

Zde **O(n)** čas a **O(n)** prostor zásobníku (jeden rámec na volání).

## Úskalí

- **Chybějící základní případ** -> nekonečná rekurze -> přetečení zásobníku.
- Hluboká rekurze může vyčerpat zásobník; některé jazyky postrádají optimalizaci tail-call.
- Přepočítávání překrývajících se podproblémů se může zvýšit na exponenciální čas (opravte memoizací).

## Proč to je důležité

Rekurze přirozeně vyjadřuje samo-podobné problémy — stromy, grafy, rozděl a panuj — mnohem čistěji než smyčky.

Je to myšlenková struktura za merge sortem, backtrackingem a dynamickým programováním.

Pochopení zásobníku volání vás také zlepšuje v ladění a uvažování o paměti.