Rekurze v Logu

Obsah

1. Rekurze v Logu
2. Rekurzivní volání procedur a problém ukončení rekurze
3. Podmíněný příkaz typu if
4. Demonstrační příklady – vykreslení spirály a dvojité spirály
5. Demonstrační příklad – nepravidelná jednoduchá či dvojitá spirála
6. Demonstrační příklady – vykreslení tří verzí spirálního útvaru
7. Odkazy na další informační zdroje
8. Obsah následující části tohoto seriálu

1. Rekurze v Logu

I've always believed that one of the most important things about scripting languages is that they (potentially) make a new class of applications more accessible to people who didn't previously think of themselves as programmers. Languages then grow up, get computer-science envy, and forget their working-class roots.
Tim O'Reilly

Rekurze, neboli volání nějaké procedury v těle té samé procedury (přímá rekurze) nebo prostřednictvím procedury jiné (takzvaná nepřímá rekurze), představuje jednu ze základních programátorských technik, na kterých je Logo postaveno. Můžeme zde spatřovat velkou inspiraci Lispem, ve kterém se rekurze také velmi často používá; ostatně samotné Lispovské příkazy, například apply, map či forall jsou definovány rekurzivně, podobně jako v dalším Lispovsky orientovaném jazyce – ve Scheme. Samotná myšlenka rekurze je však starší než všechny programovací jazyky, protože je hluboce zakořeněna jak v podstatě některých přírodních i umělých jevů či objektů, tak i v matematice, v například v definicích různých algebraických a geometrických struktur.

Na druhou stranu není podpora rekurze při programování tak samozřejmá, jak by mohlo na první pohled vypadat, protože mnoho programovacích jazyků rekurzi nepodporuje. Příkladem může být například první široce používaný programovací jazyk Fortran, klasický Basic (Visual Basic má s Basicem společné snad už jen jméno a několik nelogičností, které jsou v obou jazycích už po několik desítek let zakořeněny), některé shellovské interpretery apod. Logo však mezi tyto omezené jazyky v žádném případě nepatří, o čemž se přesvědčíme na několika demonstračních příkladech, které budou uvedeny v následujících kapitolách. Naopak – příkazy pro tvorbu iteračních smyček, které jsou v mnoha případech nedílnou a neměnitelnou součástí programovacího jazyka (C, C++, Java), je možné v Logu doprogramovat právě pomocí rekurze spojené s možností předávat část programu jako data (seznam).

Bez vysvětlování dalších podrobností (k tomu prozatím nemáme potřebné znalosti, nicméně se k této problematice samozřejmě ještě vrátíme v následujících částech tohoto seriálu) si ukažme náhradu standardního iteračního příkazu while, který můžeme najít v mnoha programovacích jazycích, nově definovaným příkazem my_while. Odlišné pojmenování bylo zvoleno z toho důvodu, že některé interpretery jazyka Logo mají vestavěnu i podporu pro iterační smyčky a mohlo by dojít ke kolizi jmen. Příkaz run, který je v dále uvedeném kódu použit pro vyhodnocení podmínky i pro spuštění těla smyčky, se podobá příkazu eval známého z dalších funkcionálních a/nebo interpretovaných jazyků s tím, že jako svůj parametr očekává seznam příkazů, které se mají spustit:

to my_while :podminka :telo
    if not run :podminka [stop]
    run :telo
    my_while :podminka :telo
end

to test_while
    make "i 0
    my_while [:i < 10][show :i make "i :i+1]
end

test_while

; výstup programu
0
1
2
3
4
5
6
7
8
9 

2. Rekurzivní volání procedur a problém ukončení rekurze

Samotný zápis rekurze, tj. zavolání nějaké procedury při běhu (provádění) té samé procedury procedury, je velmi jednoduché – uvnitř nově vytvářené procedury je použit název této procedury. Všimněte si, že není zapotřebí používat žádné pomocné syntaktické prvky typu forward (Pascal), hlavičky funkcí (C, C++) apod. Stejné pravidlo platí i při zápisu nepřímé rekurze, tj. v případě, že procedura A volá proceduru B, v jejímž těle je opět volána procedura A. Logo volání procedur (a tím i rekurzi) řeší až v době běhu programu, proto lze ve vytvářeném programu zapisovat i jména procedur, které ještě nejsou vytvořeny. Před ukázkou některých praktických příkladů rekurze si ukažme, jak se rekurze v Logu zapisuje. Vzhledem k tomu, že v následujícím kódu není použitý příkaz stop, rekurze teoreticky nikdy neskončí, konkrétní chování mj. závisí na tom, zda daný interpreter Loga podporuje takzvanou tail recursion, neboli náhradu rekurze smyčkou:

to kruznice_rekurzivne
    forward 1
    left 1
    kruznice_rekurzivne
end

draw
kruznice_rekurzivne 

Při spuštění výše uvedeného programu například v interpreteru Loga Turtle Tracks uvidíme, jak se postupně vykreslí kružnice. Po vykreslení celé kružnice bude želva pokračovat v pohybu po této kružnici až do chvíle, kdy je vypsána interní chyba StackOverflowE­rror (to sice není dobrá vizitka autora tohoto interpreteru, musíme však mít na mysli, že se jedná o nedokončený projekt). Na druhou stranu se například interpreter Loga MSW Logo chová jinak: spuštěný program se nikdy nezastaví a také neroste alokovaná paměť. Z toho vyplývá, že došlo k rozvinutí rekurzivního volání do nekonečné smyčky. Z chování obou zmíněných interpreterů i z prosté logiky (program by se měl v definované chvíli zastavit, nemůže počítat donekonečna) je zřejmé, že Logo musí obsahovat způsob, jakým je možné v závislosti na nějaké podmínce rekurzi zastavit.

Vlastní zastavení rekurze, tj. opakovaného volání té samé procedury, je provedeno ve chvíli, kdy interpreter Loga při běhu našeho programu narazí na příkaz stop. Kdyby však byl tento příkaz bez dalších náležitostí přímo vložen do těla rekurzivní procedury, došlo by k ukončení rekurze buď ihned po zavolání této procedury, nebo naopak nikdy. Ukončení či neukončení rekurze závisí na vzájemném postavení příkazu stop a rekurzivního volání. Rozdíl chování v praxi ilustrují následující dvě procedury, z nichž jedna ukončí svůj běh při svém prvním zavolání, protože interpreter ještě před provedením rekurze narazí na příkaz stop, zatímco druhá procedura teoreticky neskončí nikdy (skončit sice může, ale běhovou chybou interpreteru):

to ihned_skonci
    stop
    ihned_skonci
end

ihned_skonci

to nikdy_neskonci
    nikdy_neskonci
    stop
end

nikdy_neskonci 

Z obou výše uvedených ukázek plyne, že pro řízení ukončení rekurze je zapotřebí použít nějakou formu rozhodovacího (podmíněného) příkazu. Ten je v Logu reprezentován příkazem if a ifelse. V následující kapitole bude vysvětlen příkaz if, tj. základní verze podmíněného příkazu, zatímco jeho rozšířené verzi ifelse se budeme věnovat až v další části tohoto seriálu.

3. Podmíněný příkaz typu if

Podmínky se v Logu nejčastěji vyjadřují pomocí příkazu typu if popř. ifelse. Nejprve si řekněme, jakým způsobem se používá jednodušší z podmíněných příkazů, tj. příkaz if. Tento příkaz očekává dva parametry. Prvním parametrem je podmínka, přesněji řečeno logický výraz, který se vyhodnotí na pravdivostní hodnotu true (pravda) či false (nepravda). My jsme si prozatím neuváděli typy výrazů, které je možné v Logu použít, ale v následujících demonstračních příkladech budou použita pouze porovnání dvou číselných hodnot. Druhým parametrem příkazu if je seznam (uzavřený v hranatých závorkách), ve kterém může být obsaženo libovolné množství dalších příkazů, včetně smyček, vložených příkazů if, volání jiných procedur atd.:

if logický_výraz [
    seznam_příkazů
    další_příkaz
    a další
] 

Jakmile interpreter Loga nalezne příkaz if, provede se vyhodnocení podmínky uvedené za tímto příkazem. V případě, že se podmínka vyhodnotí na logickou hodnotu true, tj. výraz je pravdivý, je spuštěna část programu, která je uložena v seznamu za příkazem if. V opačném případě, tj. jestliže se podmínka vyhodnotí na logickou hodnotu false (výraz je nepravdivý), tak se příkazy uvedené v seznamu přeskočí a program pokračuje prvním příkazem uvedeným za if. Může také nastat situace, že za seznamem příkazu if se již nevyskytují další příkazy, tj. je zde uvedeno pouze slovo end, které ukončuje deklaraci procedury. V tomto případě je běh procedury ihned zastaven a program ve svém běhu pokračuje buď ve volající proceduře nebo (pokud žádná volající procedura neexistuje) je program korektně ukončen.

Obrázek 1: Funkce podmíněného příkazu if

4. Demonstrační příklady – vykreslení spirály a dvojité spirály

V následujícím demonstračním příkladu je ukázáno, jakým způsobem je možné zkombinovat příkaz if a rekurzi. Procedura nazvaná spirala1 očekává tři parametry: délku o kterou se má želva posunout, úhel otočení želvy po jednom kroku a přírůstek kroku želvy. Po vykreslení každé části spirály se krok želvy, tj. hodnota parametru strana, sníží o zadaný přírůstek, takže želva vykreslí následující část spirály s kratším krokem. To má za následek neustálé zmenšování vykreslovaných částí oblouků, zatímco úhel natočení zůstává stejný. Rekurzivní volání procedury spirala1 je ukončeno ve chvíli, kdy je dosaženo minimálního kroku rozumné délky, tj. jedničky (menší kroky by již vedly k vykreslení tak malé úsečky, že by nebyla viditelná). Jakmile je dosaženo kroku menšího než jedna, rekurze je ukončena, tj. program se postupně „vynořuje“ z procedury spirala1, která volala sama sebe. Zdrojový kód procedury spirala1 má následující tvar:

to spirala1 :strana :uhel :prirustek
    if :strana>1 [
        forward :strana
        right :uhel
        spirala1 :strana-:prirustek :uhel :prirustek
    ]
end

draw
pu
setxy -100 0
pd
spirala1 15 6 0.05 

Obrázek 2: Spirála vykreslená pomocí procedury spirala1

Spirála, ovšem může být vykreslena i jiným způsobem, například tak, že se postupně mění úhel natáčení želvy, zatímco její krok zůstává konstantní. Tvar této spirály je odlišný od předchozího případu, což je jasně patrné z obou screenshotů. Rekurzivní proceduru pro vykreslení druhého typu spirály lze zapsat například následujícím způsobem. Všimněte si, že se obě procedury odlišují „pouze“ způsobem výpočtu parametrů při rekurzivním volání:

to spirala2 :strana :uhel :prirustek :maxuhel
    if :uhel < :maxuhel [
        forward :strana
        right :uhel
        spirala2 :strana :uhel+:prirustek :prirustek :maxuhel
    ]
end 

Po specifikaci délky strany rovné osmi krokům želvy, počátečního úhlu 0° a přírůstku úhlu nastaveným na hodnotu 0,07° se vykreslí jednoduchá spirála. Podmínku pro ukončení rekurze je v tomto případě nutné změnit tak, aby se želva po otočení o úhel větší než 360° neotočila zpět. Při běžně používaných rozlišeních grafické plochy dostačuje podmínka pro úhel menší než 40°, při maximálním úhlu větším než 90° stejně již nedochází k vykreslování tvaru podobného spirále, ale spíše hvězdě. Jednoduchá spirála vykreslená po zadání příkazu spirala2 8 0 0.07 40, je vyobrazena na třetím obrázku.

; vykresleni jednoduche spiraly
draw
spirala2 8 0 0.07 40 

Obrázek 3: Jednoduchá spirála vykreslená pomocí procedury spirala2

V případě, že se maximální úhel, při kterém dochází k zastavení rekurze, nastaví na hodnotu větší než 180°, dojde při vykreslování spirály k zajímavému chování, protože se želva začne vracet po spirále, kterou při svém předchozím pohybu vytvořila. Toto chování je pochopitelné, stačí si uvědomit, že například otočení doleva o 1° je to stejné, jako otočení doprava o 359° a otočení doleva o 361° odpovídá otočení o 1° ve stejném směru. Po návratu do výchozí pozice je želva otočena o 180° oproti své původní pozici (protože se vrací) a při větším počtu kroků začíná vykreslovat spirálu ve druhém směru. Tímto způsobem byl vytvořen čtvrtý obrázek. Parametry použité pro vykreslení tohoto obrázku jsou uvedeny v následujícím fragmentu kódu:

; vykresleni dvojite spiraly
draw
spirala2 15 0 1 2*360 

Obrázek 4: Dvojitá spirála vykreslená pomocí procedury spirala2

5. Demonstrační příklad – nepravidelná jednoduchá či dvojitá spirála

Oba dva způsoby ovlivňování pohybu želvy při kresbě spirály, které jsme si prakticky ukázali na procedurách spirala1 a spirala2, je samozřejmě možné kombinovat. Výsledkem je jednoduchá či dvojitá nepravidelná spirála, popř. i jiný obrazec, jehož konkrétní tvar je zcela závislý na zvolených číselných hodnotách parametrů. V následující rekurzivně volané proceduře, která je pojmenována spirala3, jsou použity celkem čtyři parametry. První parametr, jenž opět udává krok želvy, je následován změnou kroku. Poté je požadována hodnota úhlu natočení želvy a přírůstek tohoto úhlu. Jak změna kroku, tak i přírůstek úhlu mohou být specifikovány kladnými i zápornými hodnotami, přičemž vzájemnou kombinací těchto hodnot je možné dosáhnout vykreslení značně různorodých tvarů:

to spirala3 :strana :ds :uhel :prirustek
    if :strana>1 [
        forward :strana
        right :uhel
        spirala3 :strana-:ds :ds :uhel+:prirustek :prirustek
    ]
end 

Příklad použití procedury spirala3 s parametry, po jejichž zadání se vykreslí obrázek číslo pět:

draw
pu
setxy 0 -200
pd
spirala3 40 0.5 20 -0.5 

Obrázek 5: Dvojitá nesymetrická spirála vykreslená pomocí procedury spirala3

6. Demonstrační příklady – vykreslení tří verzí spirálního útvaru

V šesté kapitole si ukážeme další varianty použití smyčky repeat, podmíněného příkazu if a rekurze. Procedura nazvaná spiral_object slouží k vykreslení obrazce, který je složen z jedné lomené čáry (polyčáry). Želva v programové smyčce vykresluje jednotlivé segmenty polyčáry, přičemž je postupně zvětšována jejich délka. Vzhledem k tomu, že není použita rekurze, jejíž výhoda spočívá i v implicitní alokaci pomocné paměti pro parametry, je nutné používat pomocnou proměnnou a příkaz make pro změnu hodnoty této proměnné (syntaxe tohoto příkazu je složitější, proto si ji vysvětlíme později). Úhel natočení želvy by měl být nastaven na hodnotu odlišnou od 90° a 180°; nejzajímavější obrazce vznikají tehdy, pokud se úhel natáčení nepatrně liší od pravého úhlu. Na šestém obrázku je screenshot grafické plochy Loga při zavolání procedury spiral_object s hodnotou natočení úhlu nastavenou na 85°.

to spiral_object :angle
    make "side 0
    repeat 280 [
        forward :side
        right :angle
        make "side :side + 1
    ]
end

draw
clearscreen
spiral_object 85 

Obrázek 6: Obrazec vykreslený procedurou spiral_object

Procedura spiral_object2, jejíž zdrojový kód je uveden níže, používá pro vykreslení obrazce rekurzi a tím pádem také podmíněný příkaz typu if, který je použit pro test, zda se má rekurze zastavit či nikoli. Vzhledem k tomu, že se všechny parametry předávají rekurzivně volané proceduře, není nutné používat pomocné proměnné, čímž se program zjednoduší a také zpřehlední. Další rozdíl oproti výše uvedené proceduře spiral_object spočívá v tom, že je možné specifikovat i počáteční délku segmentu polyčáry. Na sedmém obrázku je screenshot grafického okna aplikace Turtle Tracks po spuštění procedury spiral_object2 s počáteční hodnotou délky segmentu nastavenou na 5 kroků želvy a s úhlem natočení nastaveným na 89°.

to spiral_object2 :size :angle
    forward :size
    right :angle
    if :size < 200 [
        spiral_object2 :size + 2 :angle
    ]
end

draw
clearscreen
spiral_object2 5 89 

Obrázek 7: Obrazec vykreslený procedurou spiral_object2

Dnešní poslední demonstrační příklad je založen na proceduře nazvané spiral_object3 (uznávám, že se nejedná o nápadité názvy), která vznikla zobecněním předešlé procedury spiral_object2. V parametrech je možné specifikovat jak počáteční délku segmentu polyčáry a úhel natočení želvy, tak i změnu délky polyčáry. Změna by měla být kladná, jinak by došlo k nekonečné rekurzi, která by dříve či později skončila běhovou chybou. Změnou všech tří parametrů lze ovlivnit tvar výsledného obrazce, tj. jak průběh „rozvíjení“ tvaru, tak i rychlost jeho zvětšování – různé varianty jsou zobrazeny na osmém, devátém a desátém obrázku.

to spiral_object3 :size :angle :delta
    forward :size
    right :angle
    if :size < 500 [
        spiral_object3 :size + :delta :angle :delta
    ]
end

draw
clearscreen
hideturtle
spiral_object3 1 89 0.6 

Obrázek 8: Obrazec vykreslený procedurou spiral_object3

Obrázek 9: Další obrazec vykreslený procedurou spiral_object3

Obrázek 10: Odlišný obrazec vykreslený procedurou spiral_object3

7. Odkazy na další informační zdroje

Většinu důležité literatury o programovacím jazyku Logo jsme si uvedli již v předchozích částech tohoto seriálu. Vzhledem k důležitosti rekurze při zpracování různých datových struktur i při implementaci některých algoritmů bude v dnešním díle uvedena literatura, která se zabývá právě problematikou práce s (většinou nelineárními) datovými strukturami a algoritmy řešenými pomocí rekurze. Problémy popisované v této literatuře jsou sice většinou implementovány v jiném programovacím jazyce (C, Java, Pascal), princip však vždy zůstává stejný.

1. Donald Knuth:
   Structured Programming With goto Statements,
   Computing Surveys 6, 4, December 1974, pp. 261–301
2. James F. Korsh and Leonard J. Garrett:
   Data Structures, Algorithms and Program Style Using C
3. Wayne Amsbury:
   Data Structures: From Arrays to Priority Queues
4. Jon Bentley:
   The Cost of Recursion,
   Dr. Dobb's Journal, June 1998
5. Ellis Horowitz and Sartaj Sahni:
   Fundamentals of Data Structures,
   Dr. Dobb's Journal
6. Bruno R. Preiss:
   Data Structures and Algorithms with Object-Oriented Design Patterns in Java,
   Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, Canada

8. Obsah následující části tohoto seriálu

I v následující části tohoto seriálu se budeme zabývat rekurzí. Ukážeme si složitější obrazce, které je možné pomocí této silné programátorské pomůcky vykreslit. Bude se jednat například o známý Pythagorův strom nebo o různé typy fraktálních konstrukcí.