? pr [Not everyone needs to program computers.]

Na početnu stranicu! Udruga Darovitih Informatičara Rijeke Na glavni izbornik!

rekurzija

Ovo je kažu najvažnija stvar u Logo-u, ma čekaj kad te skužim!

Ovdje ćemo pokušati što jednostavnije objasniti jednu od tehnika programiranja pomoću programskog jezika Logo, a koja je vrlo karakteristična za njega i njemu slične jezike. Radi se o rekurzivnom programiranju. Pri tome ćemo se baviti samo grafičkim primjerima.

korni500.gif (1525 bytes)

Pišite na: logo@dir.hr

1. primjer: kutko :n :d
2. primjer: kvadri :x :d
3. primjer: spirkvad :x :d
4. primjer: unazad :d :r
5. primjer: vjetar :d :r :n :k

    Pretpostavljamo da niste potpuni početnik u Logo programiranju, pa ćemo krenuti s nešto više razine koja pretpostavlja poznavanje osnovnih instrukcija: 'fd',' bk', 'rt', 'lt', 'if', 'stop' i 'repeat', te pisanja procedura s ulaznim podacima (parametrima). Primjeri će biti pisani u verziji MSWLogo (Microsoft Windows Logo), koji je izgrađen na verziji UCBLogo Briana Harveya, jednog od najvećih autoriteta u ovom programskom jeziku.


1. PRIMJER

Prva procedura koju ćemo analizirati je:

to kutko :kutova :duljina
     if :kutova<3 [stop]
     repeat :kutova [fd :duljina rt quotient 360 :kutova]
end

U njoj bi nam trebalo biti sve jasno, osim možda izraza:

rt quotient 360 :kutova

O čemu se ovdje radi? Jednostavno rečeno to je isto što i:

rt 360/:kutova

samo što se umjesto infix oblika koristi prefix oblik u kome se prije parametara 360 i :kutova navodi 'quotient' čiji je izlazni podatak broj dobiven dijeljenjem njegovog prvog ulaznog parametra s drugim. Dakle, ako je :kutova=2, onda će instrukcija:

pr quotient 360 :kutova

rezultirati ispisom broja:

180

na zaslonu.

U našem sučaju će izlazni podatak od 'quotient' biti predan proceduri 'rt'. Ona će taj podatak primiti kao njen ulazni podatak.

Vratimo se samoj proceduri 'kutko :kutova :duljina' koja ima dva ulazna podatka. Ona crta pravilan poligon ili mnogokut kome možemo prvim ulaznim podatkom odrediti koliko kutova ima (:kutova) i drugim ulaznim podatkom (:duljina) kolika je duljina stranice u kornjačinim koracima (pixelima). Kako bi proceduru zaštitili od nelogičnih ulaznih podataka (npr. :kutova=2, jer ne postoji pravilan dvokut ili :kutova= -5), odmah se kao prva instrukcija u njoj provjerava pomoću 'if' vrijednost varijable :kutova, te ako je ona manja od 3 prekida se pomoću 'stop' izvođenje procedure 'kutko'. Ako je :kutova veće od 2 dolazi do izvođenja procedure 'repeat' koja crta pravilan mnogokut pripadajućih veličina. Slijede dva primjera poziva s njihovim crtežima.

NAPOMENA:

Imena varijabli bi trebala biti ovakva kao u ovom primjeru. Dakle, imena koja sama za sebe govore što predstavljaju. Međutim, zbog kraćeg koda i bržeg prepisivanja, u daljnjim primjerima ćemo za imena varijabli koristiti po jedno slovo. Neki bi se jako ljutili zbog ove odluke (prvi Brian Harvey, a drugi Hrvoje Blažević).


cs kutko 3 100
cs kutko 5 50

Ja idem na vrh stranice, a Vi?


2. PRIMJER

U gornjem primjeru nema rekurzije, ali nam je poslužio kako bi shvatili ulogu 'if' i 'stop' bez kojih rekurzija nema velikog smisla. Slijedeći primjer je prava rekurzivno napisana procedura:

to kvadri :x :d
        if or :x<1 :x>4 [stop]
        fd :d rt 90
    kvadri difference :x 1 :d
end

Procedura 'kvadri' kontrolira vrijednost x i ako je ona ili manja od 1 ili veća od 4 zaustavlja izvođenje. Ako je prihvatljiva vrijednost (brojevi 2, 3 ili 4) kornjača crta crtu duljine d i okreće se za 90 u desno. Nakon toga se izvodi instrukcija:

kvadri difference :x 1 :d

koja predstavlja rekurzivni poziv na samu proceduru. Pošto 'kvadri' ima dva ulazna podatka, onda sve nakon riječi kvadri je u stvari određivanje ulaznih podataka za rekurzivni poziv. Tako:

difference :x 1

izračunava trenutnu vrijednost x smanjenu za 1 i daje to kao svoj izlazni podatak koji postaje prvi parametar uz 'kvadri'. On je primljen opet kao x, ali novi x. Važno je napomenuti da logo sve vrijednosti x pamti. Drugi parametar za 'kvadri' je trenutna vrijednost d. Pokušat ćemo napisati što se događa od početka, od prvog poziva procedure 'kvadri' s konkretnim brojevima.


kvadri 4 100 (ovo piše korisnik, a nakon toga logo sam sve obavlja bez intervencije korisnika)
-------------------------------------
to kvadri 4 100
        if or 4<1 4>5 [stop]
        fd 100 rt 90
    kvadri difference 4 1 100
end
-------------------------------------
    kvadri 3 100
    -------------------------------------
    to kvadri 3 100
            if or 3<1 3>5 [stop]
            fd 100 rt 90
        kvadri difference 3 1 100
    end
    -------------------------------------
        kvadri 2 100
        -------------------------------------
        to kvadri 2 100
                if or 2<1 2>5 [stop]
                fd 100 rt 90
            kvadri difference 2 1 100
        end
        -------------------------------------
            kvadri 1 100
            -------------------------------------
            to kvadri 1 100
                    if or 1<1 1>5 [stop]
                    fd 100 rt 90
                kvadri difference 1 1 100
            end
            -------------------------------------
                kvadri 0 100
                -------------------------------------
                to kvadri 0 100
                        if or 0<1 4>5 [stop]

Rezultat svega će biti nacrtan kvadrat veličine stranica od 100 kornjačina koraka. Ako bi se napisalo u pozivu:

kvadri 2 50

rezultat bi bila ova slika  , tj. samo dvije stranice kvadrata.

Ja idem na vrh stranice, a Vi?


3. PRIMJER

Slijedeći primjer crta kvadratnu spiralu od vani na unutra, ako mu je drugi ulazni podatak (:d) pozitivan broj. Ako je on negativan onda crta prema van. Prvim ulaznim podatkom (:x) određujemo duljinu prve crte kvadratne spirale, a svaka slijedeća je ili manja ili veća za vrijednost drugog ulaznog podatka (:d).

to spirkvad :x :d
        if or :x<1 :x>500 [stop]
        fd :x rt 90
    spirkvad difference :x :d :d
end

Vrijednost d se ne mjenja dok se x mijenja ili na manje ili na više. Naime, ako pozovemo:

spirkvad 100 10

prva vrijednost x je 100, a slijedeća je 100-10=90, slijedeća je 90-10=80 i tako dalje dok ne postane manja od 1, kad se prekida procedura. Ako upišemo:

spirkvad 100 -5

onda je prvi x=100, a slijedeći je 100-(-5)=105, slijedeći 105-(-5)=110 i tako dok ne postane veći od 500 kada se procedura prekida.

Ja idem na vrh stranice, a Vi?


4. PRIMJER

Do sada smo imali jedostavnu rekurziju, sada ćemo obraditi primjer koji ide jedan korak dalje i dodaje instrukcije nakon rekurzivnog poziva unutar procedure.

to unazad :x :d
            if or :x<1 :x>500 [lt 90 stop]
            fd :x rt 90
        unazad difference :x :d :d
        bk :x lt 90
end

Nećemo objašnjavati što se događa s procedurom do rekurzivnog poziva, jer je sve slično kao i u primjeru broj 2. ili broj 3. Koliko god puta se aktivira linija s rekurzivnim pozivom toliko puta se crtaju crte spirale kao u primjeru broj 3. U stvari, ovaj je primjer isti kao i treći, samo što su mu dodane neke instrukcije. Rekli smo na početku da se svaka trenutna vrijednost varijable pamti, iako joj se u slijedećem prolazu vrijednost promjeni. Ona prethodna vrijednost je zapamćena. Isto tako je i zapamćena čitava instrukcija koja se nije niti izvela, a to je u ovom primjeru:

bk :x lt 90

koja se nalazi iza rekurzivnog poziva. Onoliko puta koliko se instrukcija:

fd :x rt 90

izvela crtajući spiralu korak po korak, toliko puta se 'bk :x lt 90' zapamtila neizvedena s pripadajućom vrijednošću x. Dakle, ako smo napisali:

cs unazad 70 20

onda imamo:

INSTRUKCIJA IZVEDENO ZAPAMĆENO I NEIZVEDENO
unazad 70 90 (korisnik) fd 70 rt 90 bk 70 lt 90
unazad 50 90 fd 50 rt 90 bk 50 lt 90
unazad 30 90 fd 30 rt 90 bk 30 lt 90
unazad 20 90 fd 20 rt 90 bk 20 lt 90
unazad 0 90 lt 90 stop

Nakon toga imamo kornjaču na kraju spirale (ako je kornjača vidljiva), ali posao još nije gotov. Mi ovdje prikazujemo u stvari međusliku (dodavanjem instrukcije 'wait' u kodu možete postići i taj efekt).

Nakon ovog stanja se izvodi 'lt 90 stop', tj. zaustavlja se procedura. Sada imamo četiri neizvedene ali zapamćene instrukcijske linije, koje se naknadno izvode suprotnim redoslijedom, znači:

bk 20 lt 90
bk 30 lt 90
bk 50 lt 90
bk 70 lt 90

Kornjača se tako nađe na početku spirale ali ne u istom headingu kao prije poziva na proceduru, već za 90 stupnjeva ulijevo okrenuta zbog poslijednjeg 'lt 90'.

Ja idem na vrh stranice, a Vi?


5. PRIMJER

to vjetar :d :r :n :k
        if :n<1 [stop]
        setpc (list 255 random 255 random 255)
        repeat 4 [unazad :d :r] rr :k
    vjetar :d :r :n-1 :k
end

Ovu ćete sliku dobiti, ako imate proceduru UNAZAD, MSWLogo i u njemu upišete:

cs perspective setpensize [3 3] up 20 lr 45 vjetar 150 20 10 5

Ja idem na vrh stranice, a Vi?