Alla oleva kuva voitaisiin piirtää for- tai while-silmukan
avulla. Se voidaan kuitenkin piirtää myös ilman silmukoita
määrittelemällä funktio, joka kutsuu itse itseään.
// piirretään parametrin ympyroita mukainen lukumäärä sisäkkäisiä
// ympyröitä siten, että uloimman halkaisija on d ja uloimman väri on
// joko valkoinen tai musta; sisäkkäisten ympyröiden halkaisijoiden
// erotus on 30
void piirraYmpyrat (int ympyroita, float d, boolean valkoinen)
{
// palataan jos on piirretty jo riittävästi
if (ympyroita == 0)
return;
// valkoinen tai musta ympyrä
if (valkoinen)
fill (100);
else
fill (0);
// piirretään ympyrä
ellipse (width / 2.0, height / 2.0, d, d);
// jatketaan piirtämistä, seuraavaksi pienempi jolla eri väri
piirraYmpyrat (ympyroita - 1, d - 30, !valkoinen);
}
void setup ()
{
size (400, 400);
colorMode (HSB, 100);
noLoop ();
}
void draw ()
{
// piirretään 5 ympyrää, joista uloin on piirtoikkunan levyinen ja
// väriltään musta
piirraYmpyrat (5, width, false);
}<<rekursio-sisakkaiset-ympyrat>>Alla oleva kuva esittää, miten ohjelman aikana funktiota
piirraYmpyrat() kutsutaan eri arvoilla. Viimeisessä kutsussa
parametrin ympyroita arvo on 0, jolloin funktio ei enää kutsu itseään
uudestaan. Kuvaa kutsutaan rekursiopuuksi - nimityksen syy
selviää pian.
size (18cm, 0);
usepackage ("qtree");
usepackage ("amsmath");
defaultpen (fontsize (14));
texpreamble ("\newcommand{\Circles}[1]{\texttt{piirraYmpyrat (#1)}}");
label ("\Tree [ .{\Circles{5, 400, false}} [ .{\Circles{4, 370, true}} [
.{\Circles{3, 340, false}} [ .{\Circles{2, 310, true}} [
.{\Circles{1, 280, false}} [ .{\Circles{0, 250, true}} ] ]
] ] ] ]", (0, 0));
- Rekursiossa tehtävä tai ongelma ratkaistaan pilkkomalla se pienempiin, samanlaisiin tehtäviin. Yllä olevassa esimerkissä alkuperäinen tehtävä
piirrä 5 sisäkkäistä ympyrää
ratkaistaan piirtämällä ensin uloin ympyrä ja ratkaisemalla sen jälkeen alkuperäisen ongelman kanssa samanlainen mutta pienempi ongelma
piirrä 4 sisäkkäistä ympyrää.
Pienempään ongelmaan siirtymistä kutsutaan rekursioaskeleeksi. Jotta rekursio päättyisi joskus, tarvitaan perustapaus, jota ei enää pilkota pienempiin osiin. Yllä olevassa esimerkissä perustapaus on tilanne, jossa kaikki ympyrät on piirretty.
- Rekursiivinen funktio on ohjelmoinnin tapa toteuttaa rekursio. Rekursiivinen funktio kutsuu itseään (rekursioaskel). Jotta rekursio päättyisi joskus, funktiossa täytyy olla myös lopetusehto (perustapaus). Yllä olevassa esimerkissä lopetusehto täyttyy silloin, kun kaikki ympyrät on piirretty, eli kun parametrin
ympyroitaarvo on 0.
Fibonaccin lukujono on kuuluisa esimerkki rekursiosta. Lukujono alkaa
0, 1, 1, 2, 3, 5, 8, 13, 21
Lukujonon kaksi ensimmäistä lukua ovat siis 0 ja 1, ja muut luvut ovat kahden edellisen luvun summa.
Esimerkkien helpottamiseksi sovitaan, että tässä kappaleessa
Fibonaccin lukujen indeksi alkaa nollasta, eli lukujonon
ensimmäiset jäsenet ovat:
\begin{align*}
f_0 &= 0
f_1 &= 1\
f_2 &= 1\
f_3 &= 2\
f_4 &= 3\
f_5 &= 5
\end{align*}
Alla oleva rekursiivinen ohjelma piirtää piirtoikkunan keskelle
lukujonon luvun \(f_6.\)
// palauttaa luvun f_n
int fib (int n)
{
// perustapaukset
if (n == 0 || n == 1)
return (n);
// rekursioaskel
return (fib (n - 1) + fib (n - 2));
}
<<bonacci-setup>>
void draw ()
{
text (fib (6), width / 2.0, height / 2.0);
}
Funktiokutsun fib (6) rekursiopuu näyttää seuraavalta.
usepackage ("qtree");
defaultpen (fontsize (14));
string fibtree (int n)
{
string treeBeg, treeEnd, leaves;
treeBeg = format (" [ .{\texttt{fib (%d)}} ", n);
treeEnd = " ] ";
if (n == 0 || n == 1)
leaves = format (" {\texttt{%d}} ", n);
else
leaves = " [ .+ " + fibtree (n - 1) + fibtree (n - 2) + " ] ";
return (treeBeg + leaves + treeEnd);
}
label ("\Tree " + fibtree (6));Funktiokutsun fib (6) rekursiopuusta huomataan, että esimerkiksi
Yksi tapa ongelman välttämiseen on taulukointi, jossa luku f. Taulukko alustetaan
ohjelman alussa luvuilla \(-1\), jotta ohjelmassa voidaan tunnistaa
onko arvo jo laskettu. Ohjelmassa lasketaan ja piirretään
Fibonaccin lukujonon 16 ensimmäistä lukua.
int[] f; // taulukko arvojen tallentamiseksi
// palauttaa luvun f_n
int fib (int n)
{
// jos arvoa f_n ei ole vielä laskettu...
if (f [n] < 0)
{
// lasketaan f_n ja tallennetaan taulukkoon
if (n == 0 || n == 1)
f [n] = n; // perustapaukset
else
f [n] = fib (n - 1) + fib (n - 2); // rekursioaskel
}
return (f [n]); // palautetaan arvo taulukosta
}
<<bonacci-setup>>
void draw ()
{
final int N = 15; // lasketaan f_0, f_1, ..., f_15
// varataan tila taulukolle ja alustetaan taulukko luvuilla -1
f = new int [N + 1];
for (int i = 0; i <= N; i++)
f [i] = -1;
for (int n = 0; n <= N; n++)
text (fib (n), (n + 1) * 35, height / 2.0); // 35 pikselin välein
}Alla olevassa kaaviossa toistuu sama rakenne: kaavion yläosasta lähtee kaksi haaraa, joista kukin jakautuu kahteen haaraan, joista kukin jakautuu edelleen kahteen jne.
// piirretään kaavio, jossa on annettu määrä tasoja; kaavion yläreunan
// keskikohta on annetuissa koordinaateissa (x, y), ja ensimmäisenä
// piirrettävän tason vaakaviivan pituus on parametri leveys
void piirraKaavio (int tasoja, float x, float y, float leveys)
{
if (tasoja == 0)
return;
// piirretään tämän tason vaakaviiva ja pystyviivat
float p = leveys / 2; // puolet leveydestä
float xVasen = x - p; // seuraavan tason vasemman haaran x-koordinaatti
float xOikea = x + p; // seuraavan tason oikean haaran x-koordinaatti
line (xVasen, y, xOikea, y); // vaakaviiva
float yUusi = y + p; // seuraavan tason y-koordinaatti
line (xVasen, y, xVasen, yUusi); // vasen pystyviiva
line (xOikea, y, xOikea, yUusi); // oikea pystyviiva
// rekursioaskel: piirretään vasen ja oikea haara, joissa molemmissa
// yksi taso vähemmän
int tasojaJaljella = tasoja - 1;
piirraKaavio (tasojaJaljella, xVasen, yUusi, p); // vasen haara
piirraKaavio (tasojaJaljella, xOikea, yUusi, p); // oikea haara
}
void setup ()
{
size (600, 400);
colorMode (HSB, 100);
background (0);
stroke (100);
noLoop ();
}
void draw ()
{
// kaavio, jossa on 7 tasoa; ylin taso sivusuunnassa kuvan keskellä
// ja kuvan yläreunasta 1/7 alaspäin; ylimmän tason leveys puolet
// piirtoikkunan leveydestä
piirraKaavio (7, width / 2.0, height / 7.0, width / 2.0);
}Kuvan piirtävä ohjelma voidaan kirjoittaa rekursiivisesti. Esimerkiksi 7-tasoinen kaavio voidaan piirtää
- piirtämällä ensin ylimmän tason vaakaviiva ja kaksi pystyviivaa
- piirtämällä sen jälkeen vasen ja oikea kaavio, joissa molemmissa on 6 tasoa.
Näin on tehty alla olevassa ohjelmassa.
<<rekursio-kaavio>>- Alla olevassa kuvassa vasemmanpuoleisen pystyviivan korkeus on
350 ja kunkin seuraavan pystyviivan korkeus on 10 %
edellistä pienempi. Pystyviivojen etäisyys \(x\)-akselilla on 10
pikseliä.
Tee vastaava ohjelma kopioimalla alla oleva koodi Processing-editoriin ja kirjoittamalla rekursiivisen funktion
piirraPystyviivat()runko: poista rivi<<rekursio-pystyviivat-runko>>ja kirjoita tarvittavat rivit tilalle.
// piirretään 'viivoja' kappaletta pystyviivoja siten, että // vasemmanpuoleisen pystyviivan korkeus on 'korkeus' ja // x-koordinaatti 'x' void piirraPystyviivat (int viivoja, float x, float korkeus) { <<rekursio-pystyviivat-runko>> } void setup () { size (600, 400); noLoop (); } void draw () { piirraPystyviivat (50, 10, 350); }
- Alla oleva kuva esittää eräänlaista satunnaiskävelyä, joka
etenee seuraavasti.
- Kävely lähtee liikkeelle origosta.
- Kullakin askeleella sennhetkiseen \(x\)-koordinaattiin lisätään satunnaisluku, jonka arvo on vähintään 0 mutta pienempi kuin 15. Sama tehdään \(y\)-koordinaatille. Näin saadusta askeleesta piirretään jana.
Kirjoita alla olevan ohjelmakoodin rekursiivisen funktion
satunnaiskavely()runko, eli poista rivi<<rekursio-satunnaiskavely-runko>>ja kirjoita tarvittavat rivit tilalle.
// piirretään satunnaiskävely, joka alkaa pisteestä (x, y) ja jossa on // 'askeleita' askelta void satunnaiskavely (int askeleita, float x, float y) { <<rekursio-satunnaiskavely-runko>> } void setup () { size (400, 400); noLoop (); } void draw () { satunnaiskavely (30, 0, 0); }
- Kirjoita rekursiota käyttävä ohjelma, joka piirtää alla olevan
kaltaisen kuvan.
final int VALI = 30; // lukujen välimatka kuvassa void piirraLuvut (int luku, float x) { if (luku < 0) return; text (luku, x, height / 2.0); piirraLuvut (luku - 1, x + VALI); } void setup () { size (600, 200); colorMode (HSB, 100); textAlign (CENTER, CENTER); textSize (16); background (0); fill (100); noLoop (); } void draw () { piirraLuvut (15, VALI); }
- Kolme ensimmäistä tribonaccin lukujonon lukua ovat 0, 0 ja 1, ja muut luvut ovat kolmen edellisen luvun summa. a) Kirjoita rekursioon perustuva ohjelma, joka piirtää piirtoikkunan keskelle tribonaccin lukujonon 7. luvun. Voit aloittaa kopioimalla ohjelmakoodin Fibonaccin lukujonoesimerkistä. b) Lisää ohjelmaasi taulukointi ja kirjoita ohjelma joka piirtää 16 ensimmäistä tribonaccin lukujonon lukua.
- Tee rekursioon perustuva ohjelma, joka piirtää alla olevan
“puun”.
- Puun alin haarautumiskohta on kuvan keskellä alareunassa.
- Puun seuraavat haarautumiskohdat saadaan siirtymällä nykyisestä haarautumiskohdasta yhtä pitkä matka sivusuunnassa ja ylöspäin. Alussa tämä “askel” on 100 pikseliä, ja se puolittuu joka tasolla.
- Puussa on 6 tasoa, missä kukin taso sisältää haarautumiskohdan sekä siitä lähtevät kaksi haaraa.
void piirraPuu (int tasoja, float x, float y, float askel) { if (tasoja == 0) return; float xVasen = x - askel; // vasemman haaran pää float xOikea = x + askel; // oikean haaran pää float yUusi = y - askel; // molempien päiden y-koordinaatti line (x, y, xVasen, yUusi); // vasen haara line (x, y, xOikea, yUusi); // oikea haara // rekursioaskel int tasojaJaljella = tasoja - 1; float uusiAskel = askel / 2; piirraPuu (tasojaJaljella, xVasen, yUusi, uusiAskel); piirraPuu (tasojaJaljella, xOikea, yUusi, uusiAskel); } void setup () { size (600, 400); noLoop (); } void draw () { piirraPuu (6, width / 2.0, height, 100); }
- Eri kokoisia “shakkilautoja”, joissa on vaaka- ja pystysuunnassa
\(1, 2, 4, 8, …\) ruutua - eli ruutujen lukumäärä vaaka- ja
pystysuunnassa on kahden potenssi - voidaan piirtää
rekursiivisesti.
- Perustapaus.
- Jos piirrettävää aluetta ei tarvitse enää jakaa useampaan ruutuun, piirretään ruutu (tilanteen mukaan keltainen tai musta).
- Rekursio perustapausta kohden.
- Jos piirrettävä alue täytyy vielä jakaa, jaetaan se neljään neliöön. Vasen yläkulma ja oikea alakulma merkitään piirrettäväksi mustalla, toiset kaksi neliötä keltaisella.
Alla on ohjelman piirtämiä shakkilautoja, kun jakojen määrä on 0, 1, 2 tai 4. Kirjoita ohjelma, jolla voit piirtää vastaavia kuvia.
-
<<rekursio-pystyviivat-runko>>
-
<<rekursio-satunnaiskavely-runko>>
-
<<rekursio-laskeva-lukujono>>
- a)
// palauttaa luvun t_n int trib (int n) { // perustapaukset if (n == 0) return (0); if (n == 1 || n == 2) return (n - 1); // rekursioaskel return (trib (n - 1) + trib (n - 2) + trib (n - 3)); } <<bonacci-setup>> void draw () { text (trib (6), width / 2.0, height / 2.0); }
b)
int[] t; // taulukko arvojen tallentamiseksi // palauttaa luvun t_n int trib (int n) { // jos arvoa t_n ei ole vielä laskettu... if (t [n] < 0) { // perustapaukset if (n == 0) t [n] = 0; else if (n == 1 || n == 2) t [n] = n - 1; else t [n] = trib (n - 1) + trib (n - 2) + trib (n - 3); // rekursioaskel } return (t [n]); // palautetaan arvo taulukosta } <<bonacci-setup>> void draw () { final int N = 15; // lasketaan t_0, t_1, ..., t_15 // varataan tila taulukolle ja alustetaan taulukko luvuilla -1 t = new int [N + 1]; for (int i = 0; i <= N; i++) t [i] = -1; for (int n = 0; n <= N; n++) text (trib (n), (n + 1) * 35, height / 2.0); // 35 pikselin välein }
-
<<rekursio-puu>>
- Kuvia voidaan piirtää sijoittamalla jokin luku vakion
JAOTpaikalle.void piirraShakkilauta (int jakoja, float x, float y, float sivu, boolean musta) { // perustapaus if (jakoja == 0) { if (musta) fill (0); else fill (17, 100, 100); rect (x, y, sivu, sivu); return; } // rekursioaskel float p = sivu / 2; // sivun puolikas float xOikea = x + p; // uuden jaon oikeanpuoleisten neliöiden x float yAla = y + p; // uuden jaon alaneliöiden y int jakojaJaljella = jakoja - 1; piirraShakkilauta (jakojaJaljella, x, y, p, true); // vasen ylä piirraShakkilauta (jakojaJaljella, xOikea, yAla, p, true); // oikea ala piirraShakkilauta (jakojaJaljella, x, yAla, p, false); // vasen ala piirraShakkilauta (jakojaJaljella, xOikea, y, p, false); // oikea ylä } void setup () { size (200, 200); colorMode (HSB, 100); noStroke (); noLoop (); } void draw () { piirraShakkilauta (JAOT, 0, 0, width, true); }