Revision history [back]

OK, pokud jde o to, "jak tu rekurzi sestavit":

Rekurzivní řešení často spočívá v tom, že daný problém rozdělíme na dva menší podproblémy, vyřešíme ty a následně jejich výsledky spojíme tak, aby tvořila řešení původního problému. Každý podproblém se přitom stane novým problémem, který řešíme obdobně. Dříve nebo později se dostaneme do situace, kdy ten podproblém už je triviálně řešitelný.

"Sestavení rekurze" spočívá v tom, že musíme vymyslet, jak problém rozdělit na ty menší podproblémy, jak určit, že podproblém už je triviálně řešitelný, a jak dosažená řešení podproblémů sloučit do řešení problému. Jak se to naučit nevím, asi nejspíš praxí. Ale většinou to je dost intuitivní.

Mergesort:

Zadání: Máme neseřazené pole, chceme seřazené pole.
Rozdělení: Pole rozdělíme na dvě půlky, každou seřadíme zvlášť (tj. pro každou půlku řešíme stejný typ problému, ale s menší instancí).
Sloučení: Dvě seřazená pole projdeme jedním sekvenčním průchodem, do cílového pole dáváme vždycky ten prvek, který je menší (zjednodušeně řečeno).
Detekce triviální instance: Pokud má pole právě 1 prvek, tak je nutně seřazené.

Hanojské věže:

Zadání: Máme tři tyčky A, B, C. Na tyčce A je položeno N kroužků různé velikost, vždy menší na větším. Chceme je všechny přesunout na tyčku C, přičemž můžeme přesouvat v jednu chvíli jen jeden kroužek a musíme dodžet vlastnost "menší na větším".
Rozdělení: Přesuneme N-1 kroužků z A na B (tj. řešíme stejný typ problému, ale s menší instancí).
Sloučení: Poslední zbývající kroužek přesuneme z A na C, potom přesuneme N-1 (tj. všechny) kroužků z B na C.
Detekce triviální instance: Pokud na zdrojové tyčce zbývá jen jeden kroužek, tak ho prostě přesuneme na cílovou a není co řešit.

Faktoriál: (tradiční příklad na rekurzi, ale implementačně naprosto nevhodný)

Zadání: Chceme spočítat N!.
Rozdělení: N! = N*(N-1)! (tj. pro druhý člen opět řešíme stejný typ problému, ale s menší velikostí).
Sloučení: Když už známe (N-1)!, tak to jen vynásobíme N a máme N!.
Detekce triviální instance: Z definice 1!=1, 0!=1.

Prohledávání stromu do hloubky:

Zadání: Máme strom (reprezentovaný jeho kořenem) a hledaná data.
Rozdělení: Prvek leží v listu některého z n podstromů. Podstromy prohledáváme zvlášť, každý se stává dílčím stromem (tj. stejný typ problému, menší velikost).
Sloučení: Použijeme první/poslední/všechna/atd. (podle potřeby) nalezená řešení z podstromů.
Detekce triviální instance: Pokud strom je listem, tak jen porovnáme jeho data s hledanými, a informujeme o výsledku.

Atd.