Programování pro hračičky/Opičky/Lekce 8
 Tato stránka je součástí kurzu:
| |
| středoškolská | |
| Příslušnost: skupinová | |
Rekurze editovat
Možná to někdo vyčetl z Odborného pojednání o opičkách přímo v Prazích, anebo na to někdo možná přišel sám krátce poté, co se naučil programovat složené příkazy v Lekci 3: pokud můžeme v rámci složeného příkazu použít též jiné složené příkazy, které jsme sami naprogramovali, co kdybychom použili ten příkaz, který právě programujeme? Třeba takhle:
kolečko:
sever
východ
jih
západ
kolečko
Začne-li opička vykonávat program kolečko, tak nejprve oběhne kolečko (resp. čtvereček), a pak začne vykonávat program kolečko. Je to stejný princip jako známá písnička Pes jitrničku sežral a odborně programátorsky se tomu říká rekurze.
Program kolečko ovšem nechá opičku běhat dokola donekonečna, resp. dokud ji zvenčí nezastavíme příkazem konec.[1] Kdybychom chtěli, aby se opička v určité situaci zastavila sama, museli bychom někam do programu vložit podmínku, která by tuto situaci opakovaně prověřovala:
kolečko1:
sever
východ
jih
západ
pokud nevidíš sušenku
kolečko1
Podmínky pro pokračování nebo ukončení rekurze a případně též pro různé vedlejší akce samozřejmě můžeme dle libosti zesložiťovat a využívat při tom příkazu konec rovněž uvnitř programu:[2]
kolečko2:
sever
východ
jih
západ
pokud vidíš Šneka
pokud máš hlad
pokud máš žízeň
tvař se hladově a žíznivě
jinak
tvař se hladově
potom
konec
jinak
pokud máš žízeň
tvař se žíznivě
konec
jinak
tvař se sušenkochtivě
potom
potom
potom
pokud nevidíš sušenku
kolečko2
Teď ale už doopravdy rekurze editovat
Bystřejší čtenář si jistě povšiml, že v minulé kapitole jsme se vlastně nenaučili nic nového. Všechny příklady rekurze, které jsme si zatím ukázali, totiž představovaly takzvanou koncovou rekurzi, která se dá nahradit nám již z minulé lekce známými cykly. Říci opičce na konci řady příkazů, aby začala dělat totéž od začátku, je přece ve výsledku stejný program, jako říci opičce, že tuto řadu příkazů má dělat stále dokola.
Možnosti rekurze jsou však mnohem větší. Rekurzivní volání téhož programu můžeme použít i uprostřed, a tím zajistit, že příkazy, které jsou v programu předepsány před rekurzivním voláním, se provedou stejněkrát jako příkazy, které jsou v programu předepsány po rekurzivním volání. Opička tak může například odněkud vybalit nějaké předměty, a pak je zase všechny vrátit zpět, anebo se někam vypravit, a potom zase dojít zpátky:
tamazpatky:
pokud vidíš směr sever
sever
potom
pokud vidíš směr sever
tamazpatky
potom
jih
Protože ovšem provedení jedněch a druhých příkazů stejněkrát neznamená stejný účinek v prvním i druhém případě, můžeme opičku nechat vykonávat různé akce v různém vzájemném poměru. Následující program ji například nechá dojít do poloviny cesty, která z daného místa vede rovně na sever:[3]
dopulky:
pokud vidíš směr sever
sever
potom
pokud vidíš směr sever
sever
potom
pokud vidíš směr sever
dopulky
potom
jih
Rekurzivní zavolání téhož programu můžeme také použít na více místech. Představme si třeba, že chceme, aby opička prohledala nějakou oblast, tedy aby se z každého místa podívala též do všech odboček, ale v každé odbočce, do které se dívá, se zase podívala do všech odboček... Tak by například následující program vyvedl opičku z pravoúhlého bludiště tím, že opička by postupně prozkoumala všechny možné cesty:[4]
prozkoumej:
pokud jsi venku
tvař se vítězoslavně
konec
potom
pokud vidíš směr sever
sever
prozkoumej
potom
pokud vidíš směr východ
východ
prozkoumej
potom
pokud vidíš směr jih
jih
prozkoumej
potom
pokud vidíš směr západ
západ
prozkoumej
Nepřímá rekurze editovat
Rekurze může nastat i v případě, že program nevolá sám sebe, ale jiný program, který pak volá zase onen první program. Jde potom o rekurzi nepřímou. Představme si třeba dva kratičké programy, které se takto volají vzájemně a které nechají opičku běhat střídavě na sever a na jih:
nasever:
sever
najih
najih:
jih
nasever
Jednoduché pobíhání sem a tam, které zajišťují vzájemně propojené programy nasever a najih, by se dalo snadno zařídit i jednoduchou rekurzí (anebo cyklem). Skutečné pole využití nepřímé rekurze začíná tam, kde by jednoduchá rekurze vedla k příliš složité struktuře programu (a kde by cyklus ani nestačil). Jako příklad si uveďme rozložení programu prozkoumej z minulé kapitoly této lekce do podprogramů:
venkuli:
pokud jsi venku
tvař se vítězoslavně
konec
prosever:
pokud vidíš směr sever
sever
prozkoumej
provýchod:
pokud vidíš směr východ
východ
prozkoumej
projih:
pokud vidíš směr jih
jih
prozkoumej
prozápad:
pokud vidíš směr západ
západ
prozkoumej
prozkoumej:
venkuli
prosever
provýchod
projih
prozápad
V takto zapsaném programu prozkoumej vidíme na první pohled, oč jde: opička ověří, zda už náhodou není venku, a pak postupně prozkoumá případnou odbočku na sever, na východ, na jih a na západ,[5] přičemž na každé straně opět začne prozkoumávat všechny odbočky.
Program by bylo možno dále vylepšovat — například pokusit se zajistit, aby opička pokud možno neprozkoumávala vícekrát místnosti, které už jednou prozkoumala. Rozepisovat zde takové příklady by již překročilo únosný rozsah lekce, proto to přenecháme nejbystřejším ze čtenářů. Ale můžeme prozradit, že se při tom dá dobře využít nepřímá rekurze dokonce vícenásobná.[6]
Úkoly editovat
- Vyberte si některý úkol z minulé lekce, který se vám podařilo naprogramovat pomocí cyklu, a naprogramujte jej pomocí rekurze.
- Naprogramujte příkaz, jímž opička odejde daným směrem o tolik místností, kolik předmětů určitého druhu před ní položíte — tedy například, rozhodnete-li se pro směr nahoru a pro sušenky, tak pokud před opičku položíte tři sušenky a spustíte onen příkaz, pak opička odejde o tři místnosti nahoru, ale pokud před opičku položíte sušenek pět, pak odejde nahoru o pět místností.
- Naprogramujte příkaz, po jehož spuštění opička půjde cestou vyznačenou rozmístěnými předměty určitého druhu (například sušenkami). Můžete předpokládat, že předměty jsou rozmístěny tak, aby cesta byla jednoznačná, tedy že když opička přijde do místnosti, v níž je předmět umístěn, pak kromě místnosti, z níž přišla, se předmět nachází nejvýše v jedné další místnosti.
Pracovní odkazy editovat
Poznámky editovat
- ↑ Není tomu tak úplně přesně. Pokud si to vyzkoušíme v praxi, aniž bychom cestou opičku krmili a napájeli, po nějaké době její hlad a žízeň vzrostou natolik, že opička začne panicky běhat po okolí a hledat potravu a vodu. Sice bude dále dokola vykonávat zadané pohybové příkazy, ale ze svého původního kolečka se může dostat docela daleko. A pak se ovšem také může stát, že opička někde cestou umře. Ale všechny tyhle příklady souvisí s tím, že opička je živá bytost ve hře Prahy, a pro samotné programování jsou nepodstatné.
- ↑ Následující příklad bude pro méně cvičenou opičku příliš dlouhý. Je to zkrátka příklad na objasnění principu. Přesto by neměl být pro nikoho problém jej naprogramovat, už od šesté lekce víme jak na to.
- ↑ Přesně to bude fungovat jen v případě, že na sever se dá jít sudý počet kroků. Pokud je to lichý počet kroků, nezastaví se opička v přesné polovině cesty, ale v jižní ze dvou místností, které jsou polovině nejblíže.
- ↑ I tento příklad bude pro většinu opiček příliš dlouhý. Jeho rozklad na podprogramy však vyžaduje jednu novou myšlenku. Kdo na ni nepřijde sám, najde ji osvětlenu hned v následující kapitole této lekce.
- ↑ Hloubavého čtenáře možná napadne, že vhodnější by bylo využít zde parametrů, tedy naprogramovat jeden pomocný příkaz pro všechny směry (např.
prosměr), který by se pak volal s jednotlivými potřebnými směry jako parametry (např.prosměr severatd.). Bohužel současná (květen 2020) verze opiček neumožňuje použití parametrů uvnitř podmínek. - ↑ Tedy jeden podprogram zavolá jiný, a ten zavolá zase nějaký třetí, a teprve ten třetí zavolá zase ten první. Apod.