Úloha Rekurze (Zadání) – Seminář PHP

Úloha 21: Rekurze (stromové menu a faktoriál)

Pokročilý rekurze hierarchický strom microtime() MySQL

Prozkoumejte koncept rekurze – situaci, kdy funkce volá sama sebe. V této úloze rekurzi uplatníme na dvou příkladech:

Výpis hierarchického stromu menu z databáze (strom.php): Každá položka má své id a odkaz na nadřazenou položku parent. Rekurzivní funkce dokáže vypsat neomezeně hluboce zanořený strom kategorií.
Srovnání rychlosti rekurze vs. cyklus (faktorial.php): Změříme přesný čas běhu skriptu pomocí microtime(true) a porovnáme režii rekurzivního volání funkcí oproti iterativnímu cyklu.

1. Ukončující podmínka (bázový případ): Podmínka, při jejímž splnění funkce už nevolá sama sebe, ale vrátí konkrétní hodnotu. Bez ukončující podmínky dojde k nekonečnému zacylení a přetečení zásobníku (Stack Overflow).
2. Rekurzivní krok: Funkce zavolá samu sebe s modifikovanými (zmenšenými) parametry, které se přibližují k ukončující podmínce.

Hierarchie v databázi: Položky nejvyšší úrovně mají parent = 0. Funkce GenerujMenu($parent, $uroven) vybere všechny potomky a pro každého z nich rekurzivně zavolá GenerujMenu($potomek['id'], $uroven + 1).
Měření času běhu: Funkce microtime(true) vrací aktuální unixový čas s mikrosekundovou přesností jako číslo typu float. Rozdíl $konec - $start udává dobu výpočtu v sekundách.

1. Proč bývá iterativní cyklus for u jednoduchých úloh (faktoriál, Fibonacci) rychlejší než rekurze? (Režie vytváření zásobníkového rámce / stack frame při každém volání funkce).
2. Kde je rekurze naopak přirozeným a nejlepším řešením? (Procházení stromů a grafů, složky a soubory na disku, parsování HTML/XML/JSON stromů, třídicí algoritmy jako Quicksort a Mergesort).
3. Co je to tzv. koncová rekurze (tail recursion) a optimalizace koncového volání (TCO)?