Kapitola 7: Rekurze – Nekonečné možnosti

Vítejte u jedné z nejzajímavějších a nejsilnějších kapitol celé knihy. Pokud jste někdy viděli film Inception (Počátek), kde byl sen uvnitř snu, který byl uvnitř dalšího snu, pak už máte představu o tom, co je to rekurze. Prolog nemá klasické cykly jako for nebo while, které možná znáte z jiných jazyků. Místo toho používá rekurzi – elegantní způsob, jak definovat něco pomocí sebe sama. Je to klíč k řešení složitých problémů pomocí jednoduchých pravidel.

7.1 Co je to rekurze? Matryoška v kódu

Rekurze nastává, když pravidlo ve svém těle volá samo sebe. Představte si ruskou panenku matryošku. Otevřete největší panenku a uvnitř je další, stejná, jen menší. Otevřete tu menší a je tam ještě menší. A tak dále. Kdy to skončí? Až narazíte na tu nejmenší, která už se nedá otevřít. Té nejmenší říkáme základní případ.

Obrázek 7.1: Rekurze vysvětlená pomocí robotů. Nejmenší robot drží baterii (základní případ).

7.2 Příklad: Předek (Ancestor) – Hledání kořenů

Vraťme se k naší rodinné databázi. Víme, kdo je rodič. Ale kdo je můj předek? Předek je můj rodič, nebo rodič mého rodiče, nebo rodič rodiče mého rodiče... Vidíte ten vzor?

V Prologu to zapíšeme dvěma pravidly:

% 1. Základní případ: Můj přímý rodič je můj předek.
predek(X, Y) :- rodic(X, Y).

% 2. Rekurzivní krok: Předek je rodič někoho (Z), kdo je už mým předkem.
predek(X, Y) :- rodic(X, Z), predek(Z, Y).

Představte si řetěz: Já -> Táta -> Děda -> Praděda.

• Ptám se: "Je Praděda můj předek?"
• Prolog zkusí pravidlo 2: "Je Praděda rodičem někoho, kdo je můj předek?" Ano, je rodičem Dědy.
• Teď musí zjistit: "Je Děda můj předek?"
• Znovu pravidlo 2: "Je Děda rodičem někoho, kdo je můj předek?" Ano, je rodičem Táty.
• Teď musí zjistit: "Je Táta můj předek?"
• Zkusí pravidlo 1 (Základní případ): "Je Táta můj rodič?" ANO!
• Řetěz se uzavřel, odpověď je true.

7.3 Příklad: Faktoriál a Zásobník (Stack)

Pojďme počítat. Matematický faktoriál čísla N (značíme N!) je součin všech čísel od 1 do N. Např. 5! = 5 * 4 * 3 * 2 * 1 = 120.

Rekurzivní definice:

• 0! = 1 (Základní případ)
• N! = N * (N-1)! (Rekurzivní krok)

V Prologu:

factorial(0, 1). % Základní případ: Faktoriál 0 je 1.

factorial(N, Vysledek) :-
    N > 0,
    N1 is N - 1,                 % Zmenšíme problém (o 1)
    factorial(N1, Mezivysledek), % Rekurzivní volání (vyřeš menší problém)
    Vysledek is N * Mezivysledek. % Spojíme výsledek

Jak to funguje v paměti (Zásobník/Stack):

Představte si to jako hromadu talířů v jídelně. Každé volání funkce přidá talíř nahoru. Nemůžeme vyřešit spodní talíř (5!), dokud nevyřešíme ten nad ním (4!).

1. Chci factorial(3, X). Prolog si pamatuje: "Musím vynásobit 3 * výsledek faktoriálu 2". (Přidá talíř)
2. Chci factorial(2, X). Prolog si pamatuje: "Musím vynásobit 2 * výsledek faktoriálu 1". (Přidá talíř)
3. Chci factorial(1, X). Prolog si pamatuje: "Musím vynásobit 1 * výsledek faktoriálu 0". (Přidá talíř)
4. Chci factorial(0, X). ZÁKLADNÍ PŘÍPAD! Výsledek je 1. (Odebere talíř)
5. Vrací se k 1: 1 * 1 = 1. (Odebere talíř)
6. Vrací se k 2: 2 * 1 = 2. (Odebere talíř)
7. Vrací se k 3: 3 * 2 = 6. (Odebere talíř)
8. Výsledek je 6.

Obrázek 7.2: Zásobník (Stack) jako hromada talířů. Musíme vyřešit ten nahoře, abychom se dostali k tomu dole.