Programování pro hračičky/Opičky/Lekce 8

Tato stránka je součástí kurzu:
Programování pro hračičky
středoškolská
Příslušnost: skupinová

Rekurze

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

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

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

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

Poznámky

↑ 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 sever atd.). 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.

[1] 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é.

[2] 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.

[3] 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.

[4] 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.

[5] 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 sever atd.). Bohužel současná (květen 2020) verze opiček neumožňuje použití parametrů uvnitř podmínek.

[6] Tedy jeden podprogram zavolá jiný, a ten zavolá zase nějaký třetí, a teprve ten třetí zavolá zase ten první. Apod.

[1]

[2]

[3]

[4]

[5]

[6]