Lisää esimerkkejä

Rekursion todellinen hyöty tulee esiin tilanteissa, joissa iteratiivinen ratkaisu on hankala kirjoittaa. Tarkastellaan esimerkkinä binääripuuta. Binääripuulla tarkoitetaan puurakennetta, jossa jokaisella alkiolla on korkeintaan kaksi "lasta". Binääripuu voisi siis näyttää esim. tältä (huomaa, että vaikka tietojenkäsittelijöitä pidetään joissain yhteyksissä luonnontieteilijöinä, käsityksemme puiden kasvusuunnasta on nurinkurinen):

Binääripuiden (ja puiden yleensäkin) käsittely rekursiivisesti on ainakin teoriassa helppoa: jos halutaan tehdä jokin operaatio binääripuun kaikille alkioille - esim. etsiä jokin tietty alkio puusta, voidaan kirjoittaa rekursiivinen algoritmi, joka

1. Käsittelee nykyisen alkion
2. Kutsuu itseään vasemmasta lapsesta alkavalle "alipuulle"
3. Kutsuu itseään oikeasta lapsesta alkavalle "alipuulle"

Kun koko rekursiivinen algoritmi on käsitelty, on vierailtu kerran puun jokaisessa solussa. Iteratiivinen versio algoritmista on yleensä hankalampi kirjoittaa, koska kirjanpito vieralluista alkioista menee äkkiä monimutkaiseksi.

Binääripuuta voidaan mallintaa helposti kirjoittamalla luokka, joka mallintaa yhtä alkiota puussa. Alkiolla on arvon lisäksi tieto vasemmasta ja oikeasta lapsestaan:

class Alkio:
    """ Luokka mallintaa yhtä alkiota binääripuussa """
    def __init__(self, arvo, vasen_lapsi:'Alkio' = None, oikea_lapsi:'Alkio' = None):
        self.arvo = arvo
        self.vasen_lapsi = vasen_lapsi
        self.oikea_lapsi = oikea_lapsi

Nyt jos halutaan mallintaa esimerkiksi oheisen kaltainen puu:

...se voidaan muodostaa seuraavalla ohjelmalla:

if __name__ == "__main__":
    puu = Alkio(2)

    puu.vasen_lapsi = Alkio(3)
    puu.vasen_lapsi.vasen_lapsi = Alkio(5)
    puu.vasen_lapsi.oikea_lapsi = Alkio(8)

    puu.oikea_lapsi = Alkio(4)
    puu.oikea_lapsi.oikea_lapsi = Alkio(11)

Rekursiiviset binääripuualgoritmit

Tarkastellaan ensin algoritmia, joka tulostaa kaikki binääripuun alkiot allekkain. Käytetään esimerkkinä tässä ja tulevissa tehtävissä yllä muodostettua puuta.

Funktio saa parametrikseen juurialkion (eli kaikkein ylimmäisenä olevan alkion, jonka jälkeläisiä kaikki muut alkiot ovat):

def tulosta_alkiot(juuri: Alkio):
    print(juuri.arvo)

    if juuri.vasen_lapsi is not None:
        tulosta_alkiot(juuri.vasen_lapsi)

    if juuri.oikea_lapsi is not None:
        tulosta_alkiot(juuri.oikea_lapsi)

Funktio tulostaa annetun alkion arvon, ja sen jälkeen kutsuu itseään uudestaan vasemmalle ja oikealla alipuulle (edellyttäen, että vasen ja/tai oikea alkio on määritelty). Algoritmi on melko yksinkertainen, mutta käy tehokkaasti läpi kaikki puun alkiot riippumatta puun koosta. Algoritmi ei myöskään vieraile missään puun alkiossa kahta kertaa.

Kun funktiolle annetaan parametriksi aikaisemmin luodun binääripuun juurialkio puu, se tulostaa

Vastaavalla tavalla voidaan kirjoittaa algoritmi, joka laskee kaikkien puun alkioiden summan:

def alkioiden_summa(juuri: Alkio):
    summa = juuri.arvo

    if juuri.vasen_lapsi is not None:
        summa += alkioiden_summa(juuri.vasen_lapsi)

    if juuri.oikea_lapsi is not None:
        summa += alkioiden_summa(juuri.oikea_lapsi)

    return summa

Muuttuja summa alustetaan nykyisen alkion arvolla. Tämän jälkeen siihen lisätään rekursiivisesti vasemman ja oikean alipuun summat (tarkastaen taas ensin, että ne ovat olemassa). Lopuksi summa palautetaan.

Järjestetty binääripuu

Binääripuusta on erityisesti hyötyä silloin, kun alkiot on järjestetty tietyllä tavalla. Alkion löytäminen järjestetystä puusta on nopeaa.

Tarkastellaan esimerkkinä puuta, jossa alkiot on järjestetty seuraavasti: jokaisen alkion vasen lapsi on pienempi kuin alkio itse, ja vastaavasti oikea alkio on suurempi kuin alkio itse.

Nyt alkion etsimiseen voidaan kirjoittaa rekursiivinen algoritmi, joka toimii hyvin samankaltaisesti kuin aiemmin tarkastelemamme binäärihaku: jos juurialkio on tarkasteltava alkio, palautetaan arvo True. Muuten jatketaan rekursiivisesti hakua joko vasemmasta tai oikeasta alipuusta. Jos alkio on tyhjä, palautetaan False.

def etsi_alkio(juuri: Alkio, arvo):
    if juuri is None:
        return False

    if arvo == juuri.arvo:
        return True

    if arvo > juuri.arvo:
        return etsi_alkio(juuri.oikea_lapsi, arvo)

    return etsi_alkio(juuri.vasen_lapsi, arvo)

Paluu aikaan ennen rekursiota

Harjoitellaan vielä osan lopussa hieman laajemman ohjelman tekemistä olioita hyödyntäen. Tässä tehtäväsarjassa ei rekursiota tarvitse eikä edes kannata käyttää. Listakoosteita sen sijaan pääsee hyödyntämään!

Vastaa lopuksi osion loppukyselyyn: