Seuraavan esimerkin on tarkoitus valottaa, miten rekursiota voi käyttää viikon 6 TMC tehtävissä. Kutsumme solmusta s alkavaksi alipuuksi sitä alipuuta, joka sisältää solmun s lapset ja lapsenlapset jne.
Esimerkiksi jos merkitsemme solmua s seuraavassa kuvassa punaisella:
0
/ \
0 0
/ \ \
0 0 0
/ \
0 0
niin tällöin solmista s alkava alipuu on seuraavanlainen (väritetty kokonaan punaisella):
0
/ \
0 0
/ \ \
0 0 0
/ \
0 0
Jos taas s olisi seuraava solmu:
0
/ \
0 0
/ \ \
0 0 0
/ \
0 0
niin solmusta s alkava alipuu olisi:
0
/ \
0 0
/ \ \
0 0 0
/ \
0 0
Tarkastellaampa esimerkkiä, olkoon meillä seuraavanlainen puu:
0
/ \
0 0
/ \ \
0 0 0
/ \
0 0
Tämän puun kaikissa solmuissa arvo on 0, arvot voisivat olla jotain ihan muuta vaikuttamatta puun korkeuteen. Arvoja voi kuitenkin käyttää hyödyksi visualisoimaan tämän esimerkin pointtia: asetetaan ylläolevan puiden solmujen arvoksi näistä solmuista alkavan alipuun korkeus. Nyt puumme näyttää tältä:
3
/ \
2 1
/ \ \
1 0 0
/ \
0 0
Ylläolevasta visualisaation perusteella näyttäisi siltä, että puun korkeus on aina 1 + korkeamman alipuun (oikea/vasen) korkeus. Eli esimerkiksi kun tarkastellaan punaisella merkittyä solmua seuraavassa kuvassa:
3
/ \
2 1
/ \ \
1 0 0
/ \
0 0
Sen vasemman alipuun korkeus on 1, oikean alipuun korkeus on 0 ja punaisesta solmusta alkavan alipuun korkeus on
max(1, 0) + 1 = 2.Syy tähän on varsin luonnollinen, jos haluamme päästä juurisolmuun puun juuresta, niin joudumme ensin kulkemaan toisen sen alipuiden juurien kautta. Täten saamme siis puun korkeudelle seuraavan kaavan:
korkeus(puu) = max(korkeus(puu.vasen), korkeus(puu.oikea)) + 1.Eli jos tiedämme puun kummankin alipuun korkeuden, niin voimme laskea itse puun korkeuden. Tässä rekursio astuu kuvaan.
Edellisen analyysin perusteella voisimme kuvitella, että puun korkeuden laskisi seuraava koodinpätkä:
public static int korkeus(Puu puu){
return 1+Math.max(korkeus(puu.vasen), korkeus(puu.oikea));
}
Kuitenkin jos koitat ajaa kyseistä koodia, niin huomaat ettei se toimi. Tämä johtuu siitä, että toinen rekursiivisen ratkaisun tärkeistä osista, pohjatapaus, on jätetty kokonaan huomioimatta. Emme koskaan saa koskaan oikeasti laskettua yhdenkään alipuun korkeutta, vaan yritämme aina jokaisen solmun kohdalla laskea ensin sen lapsien alipuiden korkeudet. Tämä johtaa ongelmiin viimeistään siinä vaiheessa, kun yritämme laskea sellaisen alipuun korkeutta, jota ei ole olemassa. Sopiva pohjatapaus saadaan kun muistetaan, että lehtisolmusta alkavan alipuun korkeus on 0.
Eli nyt koodimme muuttuu muotoon
public static int korkeus(Puu puu){
if(puu.oikea==null && puu.vasen==null)
return 0;
return 1+Math.max(korkeus(puu.vasen), korkeus(puu.oikea));
}
joka on jo hyvin lähellä toimivaa versiota. Jos ainoastaan toinen puun alipuista on olemassa, niin koodimme yrittää kuitenkin laskea kummankin alipuun korkeudet. Tämä saadaan kierrettyä helposti lisäämällä sopivat tarkastukset:
public static int korkeus(Puu puu){
if(puu.oikea==null && puu.vasen==null)
return 0;
int h_vasen=-1,h_oikea=-1;
if(puu.vasen != null)
h_vasen=korkeus(puu.vasen);
if(puu.oikea != null)
h_oikea=korkeus(puu.oikea);
return 1+Math.max(h_vasen, h_oikea);
}
Tämä koodi tolella laskee puun korkeuden. Visualisoidaampa tämän koodin toimintaa esimerkkipuullamme. Asetetaan kaikkien solmujen arvoksi x ja muutetaan niitä vastaamaan aina kyseisestä solmusta alkavan alipuun korkeutta sitä mukaan kun saamme korkeudet laskettua. Tietyllä hetkellä käsiteltävää solmua merkitsemme punaisella värillä.
Seuraava visualisaatio on melko pitkä, mutta se toivottavasti avaa rekursion toimintaa.
1. x / \ x x / \ \ x x x Puun vasen alipuu on olemassa, lasketaan siis sen korkeus. / \ x x
2. x / \ x x / \ \ x x x Puun vasen alipuu on olemassa, lasketaan siis sen korkeus. / \ x x
3. x / \ x x / \ \ x x x Puun vasen alipuu on olemassa, lasketaan siis sen korkeus. / \ x x
4. x / \ x x / \ \ x x x Puulla ei ole vasenta, eikä oikeaa alipuuta, joten sen korkeus on 0. / \ x x
5. x / \ x x / \ \ x x x Puun oikea alipuu on olemassa, lasketaan siis sen korkeus. / \ 0 x
6. x / \ x x / \ \ x x x Puulla ei ole vasenta, eikä oikeaa alipuuta, joten sen korkeus on 0. / \ 0 x
7. x / \ x x / \ \ x x x Puun oikean ja vasemman alipuun korkeudet on laskettu, joten sen korkeus voidaan laskea. / \ 0 0
8. x / \ x x / \ \ 1 x x Puun oikea alipuu on olemassa, lasketaan siis sen korkeus. / \ 0 0
9. x / \ x x / \ \ 1 x x Puulla ei ole vasenta, eikä oikeaa alipuuta, joten sen korkeus on 0. / \ 0 0
10. x / \ x x / \ \ 1 0 x Puun oikean ja vasemman alipuun korkeudet on laskettu, joten sen korkeus voidaan laskea. / \ 0 0
11. x / \ 2 x / \ \ 1 0 x Puun oikea alipuu on olemassa, lasketaan siis sen korkeus. / \ 0 0
12. x / \ 2 x / \ \ 1 0 x Puun vasenta alipuuta ei ole olemassa. / \ 0 0
13. x / \ 2 x / \ \ 1 0 x Puun oikea alipuu on olemassa, lasketaan siis sen korkeus. / \ 0 0
14. x / \ 2 x / \ \ 1 0 x Puulla ei ole vasenta, eikä oikeaa alipuuta, joten sen korkeus on 0. / \ 0 0
15. x / \ 2 x / \ \ 1 0 0 Puun oikean ja vasemman alipuun korkeudet on laskettu, joten sen korkeus voidaan laskea. / \ (Muista: vasemman alipuun korkeus on nyt -1, sillä sitä ei ollut olemassa!!!) 0 0
16. x / \ 2 1 / \ \ 1 0 0 Puun oikean ja vasemman alipuun korkeudet on laskettu, joten sen korkeus voidaan laskea. / \ 0 0
17. 3 / \ 2 1 / \ \ 1 0 0 Puun korkeuden laskeminen on saatu valmiiksi. / \ 0 0
Viikolla 6 ei ole (ainakaan suoraan) tehtävänä laskea binääripuun korkeutta. Tämä tapa laskea puun korkeus tuo kuitenkin esille erittäin tärkeän ajattelutavan ja on siksi mielestäni hyödyllinen esimerkki. Laskemme puun korkeuden laskemalla ensin sen alipuiden korkeudet, ja alipuiden korkeuksien avulla saamme laskettua alkuperäisen puun korkeuden. Monet puuihin liittyvistä ongelmista rakteavatkin juuri tätä ajattelutapaa hyödyntäen, esimerkkeinä: