Jak Petr vysvětloval Thomasovi rekurzi.

Když si mohl Petr vybrat, jakým způsobem se má vrhnout na danou věc, nejraději volil rekurzi, což mu způsobovalo nemalé problémy při nakupování a při sexu.

Na smazání podstromu stromové datové struktury, což byl problém, se kterým Thomas nemohl hnout, byla ale rekurze vpravdě ideální. Thomas ale rekurzi neznal, a proto byl nucen absolvovat lekci.

Přátelským hlasem Petr stručně formuloval a posléze načrtl rekurzivní volání funkce, která maže podstrom. Thomasovi se to líbilo, ale upozornil na to, že kořen podstromu může mít nejen syny, ale také vnuky. Petr pochopil, že Thomas nic nepochopil.

Pokud funkce smaže podstromy všech synů daného uzlu a pak i tento uzel, netřeba uvažovat o vnucích, říkal Petr. Ale kde takovou funkci vezmeme, ptal se Thomas. Pak upozornil na zjevnou chybu, protože v těle funkce byla tato volána.

Petr zjihl, schéma rozepsal do funkce se všemi podrobnostmi a dovolil Thomasovi, aby tu funkci přepsal do počítače. Funguje to, volal pak Thomas, a Petr šel raději nakoupit.

7 komentářů:

  1. mňo, děkuju...ale, aby ti bylo jasno, tak jen zminku: tydlecty vykricniky me hrozne prekvapily v mym rok starym sesitu matematiky, kdyz sem jim nedavno listovala. dlouhou chvili mi trvalo, nez sem si vzpomnela, co to vubec je...takze se mnou si hlavu nedelej, ja si priste budu cist uz jen prihody z nakupovani...

    OdpovědětVymazat
  2. Já tak nějak doufal, že je názorný aspoň ten faktoriál. :-) A povídání o zásobníku by se asi hodilo na jiný blog...Příští díl Petrovy cesty bude o nakupování, tak jenom doufám, že se tu někdo nevytasí s teorií nákupovaní. :-)

    OdpovědětVymazat
  3. Někomu by při vysvětlování rekurze mohlo pomoci objasnění, co se děje v paměti (tj. ukládání datových struktur do zásobníku). Formulace "součástí výpočtu rekurzívní funkce je volání té samé funkce" je sice pravdivá, ale v žádném případě názorná...

    OdpovědětVymazat
  4. Sleduj, KateřinoRekurzivní výpočet faktoriálu:faktorial 0 = 1faktorial n = n * faktorial (n - 1)Součástí výpočtu rekurzivní funkce je volání té samé funkce. Faktoriál pěti se spočítá tak, že se nejdřív spočítá faktoriál čtyř, ale k tomu je potřeba spočítat faktoriál tří, a tedy dvou, ke kterému je třeba znát faktoriál jedné, a proto si spočítáme faktoriál nuly, vynásobíme ho jedničkou a získáme 1!, tím můžeme vypočítat 2! a pak 3! a 4!, až nám nakonec vypadne těch kýžených sto dvacet. Nyní můžeš vrátit mluvidla do původního stavu a popustit si.

    OdpovědětVymazat
  5. a v papirovym slovniku je napsano: "navrat mluvidel do puvodniho stavu, popuštění"Takze sem zase nic nepochopila...

    OdpovědětVymazat
  6. ... což není úplně nejšťastnější :-))

    OdpovědětVymazat
  7. RekurzeIRC kanál #czech má jakousi encyklopedii, kde je rekurze vysvětlována takto:rekurze: viz rekurze...

    OdpovědětVymazat