Jak vypsat strom kategorií? Aneb rekurze v praxi..

Pokud jste ještě nikdy neslyšeli o rekurzivním volání funkce či metody, pak vězte, že se jedná o situaci, kdy metoda volá sama sebe. Možná, že na první pohled není patrný přínos tohto způsobu, nicméně si ho ukážeme na názorném příkladu.

Faktoriál čísla pomocí rekurze

Faktoriá čísla x (značíme x!) je roven součinu matematické řady od x do 1.  Tedy faktoriál čísla 5 lze zapsat následovně: 5! = 5*4*3*2*1 =120. U faktoriálu mimo jiné platí, že x! = x* (x-1)!. A právě toto vyjádření bude klíčem k naší první rekurzivní funkci pro výpočet faktoriálu.

Funkce v jazyce PHP může vypadat například takto:

function faktorial ($cislo){
if($cislo==0) return 1;
return $cislo * faktorial($cislo-1);

}

Pro výpočet 5! voláme faktorial(5);

Ve funkci je použita takzvaná rekurzivní podmínka, které zajistí, že se funkce nebude volat do nekonečna. V našem případě je rekurzivní podmínka postavena nad vlastností faktoriálu čísla 0, kdy faktoriál nuly je roven jedné. V případě, že je rekurzivní podmínka nesprávně uvedena, většinou funkce vrací výjimku Stack Overflow či její obdobu v jiném programovacím jazyce.

Praktické využití při výpisu stromu kategorií

Výpočet faktoriálu čísla byl spíše akademickým příkladem. Nyní si ukážeme jak použít rekurzi při výpisu kategorií. Budeme řešit složitější situaci, kdy každá kategorie může mít další podkategorie, tudíž výsledkem výpisu bude strom kategorií. Strom kategoríí je dán prostřednictvím XML s následující strukturou:


<CATEGORIES>
<CATEGORY id="1" parent="0">Notebooky</CATEGORY>
<CATEGORY id="2" parent="0">Telefony</CATEGORY>
<CATEGORY id="7" parent="1">Kancelářské</CATEGORY>
<CATEGORY id="8" parent="1">Herní</CATEGORY>
<CATEGORY id="3" parent="2">Dotykové</CATEGORY>
<CATEGORY id="4" parent="2">Klasické</CATEGORY>
<CATEGORY id="6" parent="3">Samsung</CATEGORY>
<CATEGORY id="5" parent="4">Nokia</CATEGORY>
</CATEGORIES> 

Výpis stromu kategoríí může vypadat následovně (funkce printChild je volána rekurzivně):

$doc = new DOMDocument();
$doc->load('nXML.xml');
$xpath = new DOMXpath($doc);
$firsLevel = $xpath->query("//CATEGORY[@parent='0']");
foreach ($firsLevel as $cat) {
echo $cat->nodeValue . '<br/>';
printChild($xpath, $cat);
}

function printChild($xpath, $cat, $sep = '---/') {
$catId = $cat->getAttribute('id');
$level = $xpath->query("//CATEGORY[@parent='" . $catId . "']");
if ($level->length == 0)
return;
foreach ($level as $cat) {
echo $sep . $cat->nodeValue . '<br/>';
printChild($xpath, $cat, $sep . '---/');
     }
}

Výsledek výpisu bude v našem případě vypadat takto:

Notebooky
---/Kancelářské
---/Herní
Telefony
---/Dotykové
---/---/Samsung
---/Klasické
---/---/Nokia

Je už jen na Vás, jak bude finální výpis vypadat. Stačí upravit metodu printChild podle Vašich potřeb.

A co říci závěrem? Jistě jste si všlimli, že pomocí rekurze lze elegantně řešit problémy, jejichž implementace by jinak zabrala mnohem více řádků kódu. Rekurze však v sobě srkývá i četná úskalí, mezi které patří například velmi špatné ladění a debugování rekurzivních metod a ve složitějších případech i problematické určení rekurzivní podmínky.