? pr [Not everyone needs to program computers.]
rekurzija
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.
| 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.
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
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.
| 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.
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'.
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