Neprogramátor/Kouzelné sloveso je kouzelné sloveso: rekurze

Čarodějové si velmi rádi usnadňují práci. Třeba taková chůze do schodů je únavná, a tak typického čaroděje nenapadne nic lepšího, než říci kouzelné hůlce, aby za čaroděje stoupání do schodů vyřešila.

Čarodějové dost často bydlí v různých poschodích; potřebují tedy vystoupat různý počet schodů. Navíc ale rádi sdílejí své umění s ostatními. Tohle dilema nakonec vyřešil jeden z čarodějů tím, že vymyslel kouzelnou větu

(define (vyjdi-schod ze-schodu)
  (+ 1 ze-schodu))

kterou kouzelné hůlce předal několikrát za sebou, protože aby se dostal domů, musí vyjít tři schody:

(vyjdi-schod 0)
(vyjdi-schod 1)
(vyjdi-schod 2)

1
2
3

Kouzelná věta která začíná kouzelným slovesem vyjdi-schod se tak hodí i čarodějovi, který, aby se dostal domů, potřebuje vyjít pět schodů. Jednoduše kouzelné hůlce předá kouzelnou větu vícekrát:

(vyjdi-schod 0)
(vyjdi-schod 1)
(vyjdi-schod 2)
(vyjdi-schod 3)
(vyjdi-schod 4)

Když kouzelná hůlka vykoná kouzelnou větu začínající slovesem vyjdi-schod, výsledek je číslo schodu, na kterém se čaroděj ocitne. Když jde čaroděj domů, vždycky začíná v přízemí.

Jak vytvořit nové podstatné jméno přízemí?

(define přízemí 0)

Když má čaroděj k dispozici kouzelné sloveso vyjdi-schod a kouzelné podstatné jméno přízemí, může nechat kouzelnou hůlku, aby jej dostala do třetího poschodí kouzelnými větami

(vyjdi-schod přízemí)
(vyjdi-schod 1)
(vyjdi-schod 2)

Pomocí kouzelného slovesa let* z kapitoly Neprogramátor/Pojmenování informací: definice proměnných může čaroděj místo 1 a 2 použít kouzelná podstatná jména první-schod a druhý-schod.

Jak?

(let* ((první-schod (vyjdi-schod přízemí))
       (druhý-schod (vyjdi-schod první-schod)))
  (vyjdi-schod druhý-schod))

Protože výsledek vykonání kouzelné věty je slovo kouzelného jazyka, může čaroděj výsledek, tedy kouzelné slovo, klidně použít v další větě třeba jako podstatné jméno.

Jakou mocnou kouzelnou větou vyjde čaroděj tři schody najednou?

(vyjdi-schod (vyjdi-schod (vyjdi-schod přízemí)))

Tenhle přístup ale netěší úplně všechny čaroděje. A obzvláště netěší ty, co bydlí v mrakodrapu, a musí proto domů vystoupat 20 schodů.

Vykonávání krok za krokem

Teď je nejspíš ten nejlepší čas na kouzelnický trik. Zkušenější čarodějové si dovedou představit, co asi tak kouzelná hůlka provede s kouzelnou větou, kterou čaroděj napíše nebo si někde přečte. A nebo taky ne.

Když jsou čarodějové v koncích a kouzelná hůlka po vykonání kouzelné věty odpovídá úplně něco jiného, než čaroděj čeká, může čaroději v pochopení kouzelné věty pomoci vývojové prostředí, v našem případě DrRacket, a jeho debugger.

Vykonání kouzelného dopisu kouzelnou hůlkou.
Zapnutí debuggeru ve vývojovém prostředí DrRacket.

Čaroděj může pak projít dopis pro kouzelnou hůlku krok za krokem.

Kliknutím na Step čaroděj "krokuje" vykonávání dopisu pro kouzelnou hůlku.
V jakém kroku vykonání hůlka je značí zelený trojúhelník a jakou hodnotu mají kouzelná podstatná jména zobrazuje okno Variables.
Po vykonání kouzelné věty se výsledek kouzelné věty ukáže v okně výpisu.
Po proklikání všech kroků dopisu pro kouzelnou hůlku se v okně výpisu objeví "zobáček" > značící konec (programu).

Jak vypadá krokování při použití kouzelného slovesa let*?

Jak vypadá krokování mocné kouzelné věty?

Při procházení obrázků (občas se říká screenshotů) vývojového prostředí DrRacket z krokování (občas se říká ladění nebo debugování) dopisu pro kouzelnou hůlku (občas se říká zdrojového kódu) je zajímavé si všimnou okna Stack (vpravo nahoře). Okno Stack říká, v jaké kouzelné větě se právě nachází kouzelná hůlka, která kouzelné věty vykonává. (V okně se zdrojovým kódem je aktuálně vykonávaná věta označena zeleným trojúhelníkem na začátku a zeleným kolečkem na konci. V okně Stack je vyznačena tučně.) Třeba


(vyjdi-schod ...)
(let* ...)

říká, že kouzelná hůlka ve větě začínající kouzelným slovesem let* narazila na kouzelnou větu začínající kouzelným slovesem vyjdi-schod a nejprve musí vykonat kouzelnou větu začínající vyjdi-schod, aby mohla pokračovat ve vykonávání kouzelné věty začínající kouzelným slovesem let*.

Podobně je to v případě, když okno Stack zobrazí


(+ ...)
(vyjdi-schod ...)
(let* ...)

protože kouzelná věta, která začíná kouzelným slovesem vyjdi-schod (a zároveň je v tomto případě uvnitř kouzelné věty začínající let*) obsahuje kouzelnou větu, která začíná kouzelným slovesem +.

Kolik řádků nejvíce bude zobrazeno v okně Stack při krokování následující mocné kouzelné věty?

(vyjdi-schod (vyjdi-schod (vyjdi-schod přízemí)))

Čtyři:


(+ ...)
(vyjdi-schod ...)
(vyjdi-schod ...)
(vyjdi-schod ...)

Stoupej dokud nejsi doma

Jedním ze způsobů, jakým může čaroděj vytvořit mocnou kouzelnou větu je tedy ten, že do kouzelné věty čaroděj znovu a znovu "vnoří" další kouzelnou větu, která začíná stejným slovesem, jako třeba

(vyjdi-schod (vyjdi-schod (vyjdi-schod přízemí)))

Čaroděj, který bydlí až na dvacátém schodu, musí tedy věty vnořit dvacetkrát:

(vyjdi-schod (vyjdi-schod (vyjdi-schod (vyjdi-schod (vyjdi-schod (vyjdi-schod (vyjdi-schod (vyjdi-schod (vyjdi-schod (vyjdi-schod (vyjdi-schod (vyjdi-schod (vyjdi-schod (vyjdi-schod (vyjdi-schod (vyjdi-schod (vyjdi-schod (vyjdi-schod (vyjdi-schod (vyjdi-schod přízemí))))))))))))))))))))

Když ale čaroděj, nebo i ne-čaroděj, jde domů a stoupá po schodech, tak schody nepočítá. Ne-čaroděj to pozná podle vstupních dveří nebo rohožky. Čaroděj se zeptá kouzelné hůlky třeba kouzelnou větu

(define (jsem-doma? schod)
  (if (= 3 schod)
      #t
      #f))

nebo kouzelnou větou

(define (jsem-doma? schod)
  (if (= 20 schod)
      #t
      #f))

No a když čaroděj naučil kouzelnou hůlku kouzelným slovesům vyjdi-schod a jsem-doma?, chtěl by, aby kouzelná hůlka pochopila, když ji čaroděj řekne (stoupej-dokud-nejsem-doma přízemí):

(define (stoupej-dokud-nejsem-doma ze-schodu)
  (if (jsem-doma? ze-schodu)
      ze-schodu ; jsem doma!
      (stoupej-dokud-nejsem-doma (vyjdi-schod ze-schodu))))

Jak může vypadat celý dopis pro kouzelnou hůlku čaroděje, který bydlí ve třetím patře?

#lang racket

(define (vyjdi-schod ze-schodu)
  (+ 1 ze-schodu))

(define přízemí 0)

(define (jsem-doma? schod)
  (if (= 3 schod)
      #t
      #f))

(define (stoupej-dokud-nejsem-doma ze-schodu)
  (if (jsem-doma? ze-schodu)
      ze-schodu ; jsem doma!
      (stoupej-dokud-nejsem-doma (vyjdi-schod ze-schodu))))

(stoupej-dokud-nejsem-doma přízemí)

První řádek dopisu pro kouzelnou hůlku, tedy #lang racket, je typický pro programovací jazyk Racket. Programovací jazyk Racket rozšiřuje jiný programovací jazyk, Scheme, který #lang ... nepoužívá.

A jak může vypadat dopis čaroděje, který bydlí v tom dvacátém?

#lang racket

(define (vyjdi-schod ze-schodu)
  (+ 1 ze-schodu))

(define přízemí 0)

(define (jsem-doma? schod)
  (if (= 20 schod)
      #t
      #f))

(define (stoupej-dokud-nejsem-doma ze-schodu)
  (if (jsem-doma? ze-schodu)
      ze-schodu ; jsem doma!
      (stoupej-dokud-nejsem-doma (vyjdi-schod ze-schodu))))

(stoupej-dokud-nejsem-doma přízemí)

V tuhle chvíli je dobrý nápad v DrRacket spustit debugger. Určitě není potřeba všechno hned pochopit. Jistě se ale vyplatí se teď trochu potrápit a sledovat, jaká kouzelná věta se při kterém kroku vykoná (zelený trojúhelník a kolečko a tučný řádek v okně Stack), jakou hodnotu právě mají kouzelná podstatná jména (proměnné, okno Variables) a jak to všechno dopadne (okno s výsledkem, kde je nakonec >).

Čaroděj kouzelnou hůlku naučil nové kouzelné sloveso stoupej-dokud-nejsem-doma. Pro to, aby se nové kouzelné sloveso kouzelná hůlka naučila, použil čaroděj kouzelná slovesa jsem-doma?, vyjdi-schod a ... stoupej-dokud-nejsem-doma! Takovému přístupu se říká rekurze.

Rekurze je mocná a nebezpečná. Mocná je proto, že pomáhá čaroději bydlícím ve dvacátém patře se psaním dopisů pro kouzelnou hůlku. Nebezpečná je proto, že se může stát, že čaroděj bude stále stoupat vzhůru a nikdy se domů nedostane. Třeba když bydlí ve sklepě a číslo schodu je proto -1.

Proč se čaroděj bydlící ve sklepě nikdy nedostane domů?

Protože čaroděj v kouzelném dopise říká kouzelné hůlce (stoupej-dokud-nejsem-doma přízemí). Kouzelné podstatné jméno přízemí je 0 a kouzelné sloveso vyjdi-schod způsobí, že čaroděj vždy stoupá vzhůru. Čaroděj proto nikdy neklesá a z přízemí (0) se tak nemůže dostat do sklepa (-1).

To, aby kouzelná hůlka vykonávání kouzelné věty dokončila, zajišťuje ukončující podmínka. V případě kouzelné věty začínající kouzelným slovesem stoupej-dokud-nejsem-doma je ukončující podmínka jsem-doma?. V každém kroku kouzelná hůlka zkontroluje, jestli se čaroděj ze-schodu dostane domu. Jestli ano, vrátí ze-schodu, tedy číslo schodu, na kterém čaroděj bydlí. Jestliže ale kouzelná hůlka vykoná kouzelnou větu (jsem-doma? ze-schodu) a ona kouzelná věta neplatí (vrátí #f), kouzelná hůlka stoupej-dokud-nejsem-doma (ano, tady nesedí skloňování, česky by se napsalo, že kouzelná hůlka "stoupá dokud [čaroděj] není doma") ze schodu (vyjdi-schod ze-schodu). (vyjdi-schod ze-schodu) je kouzelná věta, kterou kouzelná hůlka nejprve vykoná, čímž se dostane na schod o jeden výše, a teprve potom vykoná kouzelnou větu (stoupej-dokud-nejsem-doma ze-schodu-o-jeden-výše). (Kde kouzelné podstatné jméno ze-schodu-o-jeden-výše je výsledek vykonání kouzelné věty (vyjdi-schod ze-schodu).)

V tuhle chvíli je dobrý nápad znovu v DrRacket spustit debugger.

Navíc je asi ten správný čas zmínit Indukci -- rekurze je paralela matematické indukce. První krok matematické indukce odpovídá tomu, když platí ukončující podmínka. Indukční krok pak zajišťuje pokračování ve vykonávání [rekurzivní funkce] v případě, že ukončující podmínka neplatí. (Rekurzivní funkce je v tomto případě kouzelná věta začínající kouzelným slovesem stoupej-dokud-nejsem-doma.)

Vyjdi počet schodů

Problémy se dají řešit mnoha způsoby a stejně tak i problém čarodějů, kteří se snaží domů vystoupat po schodech. Někteří čarodějové si totiž nepamatují, kde bydlí. Za to si ale pamatují, kolik že to mají vystoupat schodů, aby se dostali domů.

Slovosled kouzelného jazyka se trochu liší, čaroděj tedy kouzelnou hůlku naučí, aby rozuměla kouzelné větě (vystoupej-schodů 3) a (vystoupej-schodů 20):

(define (vystoupej-schodů zbývá-počet)
  (if (= 0 zbývá-počet)
      zbývá-počet ; jsem doma!
      (vystoupej-schodů (- zbývá-počet 1))))

Jenže vykonání takové věty nefunguje úplně tak, jak by si čaroděj přál:

(vystoupej-schodů 3)

(vystoupej-schodů 20)

Jak čaroděj pozná, že kouzelné sloveso vystoupej-schodů funguje, jak má?

Použije debugger vývojového prostředí DrRacket.

Důvod, proč kouzelná hůlka po vykonání kouzelné věty vrátí 0 je ten, že kouzelná hůlka odpočítává, jaký zbývá-počet schodů, než čaroděj dojde domů. Když nezbývá žádný schod, takže platí kouzelná věta (= 0 zbývá-počet), čaroděj je doma. Proto kouzelná hůlka po vykonání kouzelné věty vrátí 0.

Čarodějové ale mohou kouzelné věty různě kombinovat a vkládat do sebe. Aby kouzelná hůlka pořád odpočítávala správný počet schodů, ale vracela číslo schodu, na kterém čaroděj bydlí, mohou čarodějové použít třeba kouzelnou větu

(define (vystoupej-schody-domů kolik-schodů)
  (vystoupej-schodů kolik-schodů)
  kolik-schodů)

kterou potom použijí, jak jsou zvyklí:

(vystoupej-schody-domů 3)

(vystoupej-schody-domů 20)

Opět je čas na debugger vývojového prostředí DrRacket a na prověření toho, že kouzelná hůlka dělá, co dělat má.

Shrnutí rekurze

Rekurze je, když čaroděj používá nové kouzelné sloveso ve chvíli, kdy kouzelnou hůlku ono nové kouzelné sloveso učí.

(define (počítej-do-dvaceti z-čísla)
  (if (= 20 z-čísla)
      z-čísla
      (počítej-do-dvaceti (+ 1 z-čísla))))

(počítej-do-dvaceti 11)

V příkladu výše je rekurzivní funkce počítej-do-dvaceti a ukončující podmínka (= 20 z-čísla).

Rekurze se dá použít kdekoli je potřeba nějaké opakování a typickým příkladem může být věta

(sečti-čísla-mezi 3 6)

kde kouzelné sloveso sečti-čísla-mezi je

(define (sečti-čísla-mezi menší větší) ; včetně
  (if (= menší větší)
      větší
      (+ menší (sečti-čísla-mezi (+ 1 menší) větší))))

Kouzelné sloveso je kouzelné sloveso: rekurze

Neprogramátor/Nekonečná podstatná jména: seznamy ►