Recursion | Základy algoritmizácie a programovania (2023/2024)

Zhrnutie prednášky

Prednáška vysvetľuje princíp rekurzie, teda definovanie algoritmu pomocou seba samého, na príklade generovania Fibonacciho postupnosti robotom Karlom. Keďže Karel nepracuje s premennými ani matematickými výpočtami, jednotlivé čísla postupnosti sa reprezentujú počtom značiek položených na políčkach a ich súčet sa dosahuje kopírovaním značiek z dvoch predchádzajúcich pozícií. Kľúčovou funkciou je copy_beers, ktorá zdvihne jednu značku, položí ju späť aj na novú pozíciu, a ak zostávajú ďalšie značky, rekurzívne zavolá samu seba, pričom každé volanie beží ako samostatná inštancia v pamäti. Prednáška zdôrazňuje nutnosť správne definovanej ukončovacej podmienky (if beers present), keďže jej absencia alebo zlé nastavenie vedie k nekonečnému reťazeniu volaní a vyčerpaniu pamäte. Na záver sa demonštruje aj chyba spôsobená vynechaním posledného volania funkcie na konci riadku, ktorá spôsobí ignorovanie poslednej pozície vo svete.

• - Rekurzia je definovanie funkcie/algoritmu pomocou seba samej.
• - Fibonacciho postupnosť sa u robota Karla realizuje počtom značiek namiesto matematických výpočtov.
• - Kopírovanie značiek (copy_beers) rieši súčet dvoch predchádzajúcich čísel postupnosti.
• - Funkcia copy_beers sa volá rekurzívne, kým sú na pozícii ešte značky na zdvihnutie.
• - Každé rekurzívne volanie funkcie beží ako samostatná inštancia v pamäti súbežne s pôvodným volaním.
• - Chýbajúca alebo nesprávna ukončovacia podmienka pri rekurzii vedie k nekonečnému volaniu a vyčerpaniu pamäte.
• - Zabudnuté extra volanie funkcie na konci cyklu spôsobí ignorovanie poslednej pozície vo svete.

Zhrnutie pripravené s pomocou AI z prepisu videa.