Kapitola 12: Optimalizace – Koncová rekurze (Tail Recursion)

Rekurze je krásná a elegantní, ale má jednu temnou stránku. Žere paměť. Představte si, že počítáte faktoriál čísla 1 000 000. Váš program si musí pamatovat milion "otevřených" volání (milion talířů na sobě), než se dostane k výsledku. Většinou to skončí chybou Stack Overflow (Přetečení zásobníku). Program spadne. Jak to vyřešit? Musíme psát kód chytřeji, aby si Prolog nemusel nic pamatovat.

12.1 Co je to koncová rekurze? Předání štafety

Koncová rekurze je speciální styl psaní pravidel, kde rekurzivní volání je to úplně poslední, co pravidlo udělá. Prolog v tomto případě umí použít trik zvaný Tail Call Optimization (TCO). Zahodí starou paměť, protože už ji nepotřebuje. Je to jako předání štafetového kolíku. Běžec předá kolík a může odejít z dráhy. Nemusí tam stát a čekat, až se ten druhý vrátí.

KONCOVÁ REKURZE (TAIL RECURSION) Typ rekurze, kde rekurzivní volání je poslední operací v těle pravidla. Umožňuje optimalizaci paměti.
AKUMULÁTOR (ACCUMULATOR) Pomocná proměnná, kterou si předáváme v rekurzi a ve které si průběžně "střádáme" mezivýsledek.
Štafetový běh (Koncová rekurze)
Obrázek 12.1: Koncová rekurze jako štafetový běh. Běžec předá kolík (akumulátor) a může odejít.

12.2 Příklad: Faktoriál s akumulátorem

Klasická (špatná) rekurze:

fact(N, R) :-
    N1 is N - 1,
    fact(N1, R1),   % Čekáme na výsledek R1...
    R is N * R1.    % ...abychom ho mohli vynásobit. Musíme si pamatovat N!

Koncová (dobrá) rekurze:

Použijeme pomocný predikát s akumulátorem. Na začátku je akumulátor 1.

% Hlavní pravidlo pro uživatele (obal)
fact(N, R) :- fact_acc(N, 1, R).

% Základní případ: Když jsme u 0, výsledek je to, co jsme nastřádali v Akumulátoru.
fact_acc(0, Acc, Acc).

% Rekurzivní krok
fact_acc(N, Acc, R) :-
    N > 0,
    NewAcc is Acc * N,       % Vypočítáme mezivýsledek HNED TEĎ
    N1 is N - 1,
    fact_acc(N1, NewAcc, R). % Předáme ho dál. Nic si nemusíme pamatovat!

Jak to běží:

Klíčový koncept: Paměť vs. Čas

Optimalizace pomocí koncové rekurze šetří paměť (zásobník neroste), ale vyžaduje trochu jiný způsob myšlení. Místo "až se vrátíš, tak to spočítám" říkáme "tady máš, co jsem zatím spočítal, a běž dál".

Otázky k zamyšlení

  1. Proč potřebujeme u koncové rekurze pomocný predikát (např. fact_acc)? Proč nestačí jen fact?
  2. Co je to "Stack Overflow" a jak mu koncová rekurze zabraňuje?
  3. Představte si, že sčítáte mince v peněžence. Jak by vypadal postup "klasické rekurze" (vysypat vše na stůl a počítat) a "koncové rekurze" (brát po jedné a pamatovat si mezisoučet)?

🧪 Laboratoř: Zrychlujeme kód