Mikä on WikiWiki?
nettipäiväkirja
koko wiki (etsi)
viime muutokset
Rekursio on tapa käsitellä mielivaltaisen suuria tietorakenteita. Esimerkiksi puu voi olla kuinka syvä vain, lista kuinka pitkä vain, jne. Teknisesti rekursio on erittäin yksinkertainen asia: se tarkoittaa, että ohjelman määrittelyssä käytetään apuna ohjelmaa itseään.
Rekursion toiminta perustuu siihen, että tietorakenteen operaatio palautetaan sen osan samaan operaatioon. Esimerkiksi luvun n tulo luvun m kanssa palautuu luvun n - 1 tuloon luvun m kanssa ja listan summa palautuu listan loppuosan summaan:
Rekursion päättyminen perustuu siihen, että tietyissä tapauksissa tulos ei määrity rekursiivisesti. Esimerkiksi nollan tapauksessa kahden luvun tulo on aina 0, ja tyhjän listan tapauksessa listan summa on aina 0.
Näiden tietojen perusteella on mahdollista antaa kokonaislukujen tulolle ja listan summalle määritelmät Pythoniksi:
def product(n, m):
if n == 0: return 0
return m + product(n - 1, m)
def sum(ls):
if ls == []: return 0
return ls[0] + sum(ls[1:])
Rekursiossa on yleinen idea, että isoa ongelmaa jaetaan pienemmiksi osiksi, kunnes osat ovat niin pieniä, että vastaus on triviaali. Pienistä osista sitten koostetaan isompien kokonaisuuksien tulos.
Otamme esimerkin siitä, kuinka puun koko on laskettavissa sen osien koosta. Puun koko (eli kuinka monta lehteä ja haaraa puussa on) on triviaali, kun kyseessä on lehti: lehdessä on aina yksi lehti. Haaran tapauksessa taas koko puun koko on sen molempien oksien koon summa lisättynä yhdellä (jotta myös tämä haara itse tulisi lasketuksi). Saamme tällaisen määritelmän:
def puun_koko(puu):
if lehtiko(puu): return 1
return puun_koko(vasen_haara(puu)) + puun_koko(oikea_haara(puu)) + 1
Tarkastelemme, miten puun koko lasketaan seuraavalle puulle:
/\
/ \
/ \
/\ /\
/\ \ ' `
' ` `
Merkitsemme ensin lehtien koot, koska ne on triviaalisti määritelty:
/\
/ \
/ \
/\ /\
/\ \ 1 1
1 1 1
Vain lehtiä sisältävien haarojen koko määrittyy myös helposti: koska vasemman alihaaran koko on 1 ja oikean 1, haaroja ja lehtiä on yhteensä 3:
/\
/ \
/ \
/\ 3
3 \ /\
/\ 1 1 1
1 1
Koko puun vasen alihaara on kooltaan siis 3 + 1 + haara itse eli 5. Ja lopuksi, koko puun koko on vasemman alihaaran koko 5 + oikean alihaaran koko 3 + tyvessä oleva haara 1, eli 9.
9
/\
/ \
/ \
5 \
/\ 3
3 \ /\
/\ 1 1 1
1 1
Voimme myös tarkastella, miten listan summaaminen määrittyy aina lyhyempien listojen perusteella:
sum([1,2,3]) = 1 + sum([2,3])
= 1 + (2 + sum([3]))
= 1 + (2 + (3 + sum([])))
= 1 + (2 + (3 + 0))
= 1 + (2 + 3)
= 1 + 5
= 6
Tässäkin siis listan summa lasketaan aina pienemmän listan summan avulla. Kun lista on pienentynyt tyhjäksi asti, vastaus on triviaali, eikä rekursiota tarvitse enää jatkaa.
Rekursio on induktiivisen tietotyypin luonnollinen käsittelytapa. Induktiivisia ovat (epätarkasti) tietotyypit, jotka voivat sisältää osanaan saman tietotyypin toisia arvoja. Esimerkiksi puun oksa on sekin puu, joten tietotyyppi on induktiivinen. Induktiivisessa tietotyypissä on myös perustapauksia, jotka eivät sisällä osinaan toisia saman tietotyypin arvoja. Puissa lehdet ovat tällaisia perustapauksia.
Myös listoja voi käsitellä induktiivisena tietotyyppinä siten, että hahmottaa ei-tyhjän listan koostuvan kahdesta osasta: listan ensimmäisestä elementistä ja listan loppuosasta, joka on myös lista (siispä lista on induktiivinen tietotyyppi). Listojen tapauksessa erityistapaus, joka ei sisällä muita listoja, on tyhjä lista [].
Kun induktiivista tietotyyppiä käsitellään, tietotyyppiä käsittelevässä funktiossa on oma käsittelytapansa perustapauksille ja induktiivisille tapauksille (sekä mahdollisesti näitäkin useampia). Esimerkiksi puuta käsittelevässä funktiossa katsotaan ensin, onko kyseessä lehti vai haara, ja sitten tehdään jotain triviaalia lehden tapauksessa ja jotain rekursiivista haaran tapauksessa. Jos siis kyseessä on haara, kutsuu funktio itseään rekursiivisesti haaran alipuille, ja tuottaa tuloksen jotenkin näiden kutsujen perusteella.
(Kaksi ensimmäistä esimerkkiä ja viimeinen löytyvät Pythonista sisäänrakennettuina palveluina, joten niiden pääasiallinen tarkoitus on näyttää, kuinka nekin voi määrittää rekursiivisesti.)
Listan pituus määrittyy rekursiivisesti siten, että tyhjän listan pituus on 0 ja ei-tyhjän pituus on yhtä suurempi kuin sen listan pituus, josta puuttuu ensimmäinen elementti. Eli siis:
def length(ls):
if ls == []: return 0
return 1 + length(ls[1:])
Jos rekursiiviselle funktiolle syötteitä on useampia, voimme hajottaa niistä pienemmiksi, mitä haluamme. Pääasia, että jossain vaiheessa saavutetaan triviaali tapaus. Esimerkkinä olkoon kahden listan liittäminen peräkkäin. Triviaali tapaus on se, kun toinen listoista on tyhjä: silloin tuloksena on toinen lista, sillä mikä tahansa lista yhdistettynä tyhjään listaan on sama lista. Ei-tyhjän listan tapauksessa yhdistämme listan loppuosan toiseen listaan ja liitämme tuloksen alkuun listan ensimmäisen elementin:
def put_element(element, ls):
return [element] + ls
def append(ls1, ls2):
if ls1 == []: return ls2
return put_element(ls1[0], append(ls1[1:], ls2))
Tarkastelemme, miten tällainen laskenta etenee:
append([a, b], [c, d]) = put_element(a, append([b], [c, d])) = put_element(a, put_element(b, append([], [c, d]))) = put_element(a, put_element(b, [c, d])) = put_element(a, [b, c, d]) = [a, b, c, d]
Mutta yhtä hyvin voimme hajottaa molempia listoja osasiinsa. Esimerkiksi, jos haluamme yhdistää kahdesta nousevassa numerojärjestyksessä olevasta listasta numerot yhdeksi nousevassa numerojärjestyksessä olevaan listaan, hajotamme jommankumman listoista sen mukaan, kummassa ensimmäinen numero on pienempi. Tyhjän listan tapaukset pitää tietysti ottaa huomioon ensin, koska tyhjässä listassa ei ole ensimmäistä numeroa.
Jos jompikumpi listoista on tyhjä, tuloksena on toinen lista, sillä tyhjän listan numerot lisättynä mihin tahansa listaan tuottaa kyseisen listan. Muussa tapauksessa katsotaan, kumpi listoista sisältää pienemmän numeron (listojen pienimmät numerot ovat aina niiden alussa, koska ne ovat nousevassa numerojärjestyksessä). Sitten yhdistetään rekursiivisesti listat lukuun ottamatta tuota pienintä numeroa ja liitetään pienin numero tuloksen alkuun. Määritelmä näyttää tältä:
def merge(ls1, ls2):
if ls1 == []: return ls2
if ls2 == []: return ls1
if ls1[0] < ls2[0]: return put_element(ls1[0], merge(ls1[1:], ls2))
return put_element(ls2[0], merge(ls1, ls2[1:]))
merge()-funktiokin palautuu pakosti ennemmin tai myöhemmin siihen
triviaaliin tapaukseen, jossa jompikumpi syötelistoista on tyhjä, koska
jokaisella rekursiivisella kutsulla jommastakummasta syötelistasta on
tiputettu pois ensimmäinen elementti.
Esimerkki laskennan etenemisestä (katso itse, mikä if-haara merge-funktiosta toteutuu missäkin vaiheessa):
merge([1, 3], [2, 4]) = put_element(1, merge([3], [2, 4])) = put_element(1, put_element(2, merge([3], [4]))) = put_element(1, put_element(2, put_element(3, merge([], [4])))) = put_element(1, put_element(2, put_element(3, [4]))) = put_element(1, put_element(2, [3, 4])) = put_element(1, [2, 3, 4]) = [1, 2, 3, 4]
Joskus haluamme hajottaa molempia argumentteja yhtaikaa. Esimerkiksi, haluamme asettaa kaksi listaa eräänlaiseen "aakkosjärjestykseen", eli verrata niitä ensimmäisen elementin suhteen, mutta jos 1. elementit ovat samat, 2. elementin suhteen, jne. Triviaaleja tapauksia on peräti neljä kappaletta: jompikumpi listoista on tyhjä, tai ensimmäiset elementit eivät ole samat (joko toinen on pienempi kuin toinen tai toisin päin).
Ensin testataan, onko jompikumpi listoista tyhjä, koska näissä tapauksissa emme voi testata ensimmäistä elementtiä. Määrittelemme tyhjän listan kaikkia muita ennemmäksi aakkosjärjestyksessä. Sitten verrataan listojen ensimmäistä elementtiä. Jos siitäkään ei ole apua, verrataan listojen loppuosia rekursiivisesti. Koska ensimmäisen elementin ollessa sama listojen aakkosjärjestys on sama kuin niiden loppuosien järjestys, palautetaan rekursiivisen kutsun tulos sellaisenaan.
def list_earlier(ls1, ls2):
if ls2 == []: return False
if ls1 == []: return True
if ls1[0] < ls2[0]: return True
if ls2[0] < ls1[0]: return False
return list_earlier(ls1[1:], ls2[1:])
Esimerkki laskennan etenemisestä:
list_earlier([1, 2, 3], [1, 2]) = list_earlier([2, 3], [2]) = list_earlier([3], []) = False
Pythonin listat ovat rakenteeltaan sellaisia, että niitä voi toki hajottaa osiksi muutenkin kuin irrottamalla niistä aina ensimmäisen elementin. Viimeisen elementin irrottaminen käy aivan yhtä hyvin. Listan voi myös jakaa keskeltä kahtia ja tehdä rekursiivisen kutsun molemmille puolikkaille. Tällä tekniikalla voi toteuttaa hyvin tehokkaan tavan järjestää listan suuruusjärjestykseen.
Idea on se, että jos lista on "tarpeeksi lyhyt" (1 tai 0 elementtiä), se on valmiiksi järjestyksessä. Muissa tapauksissa listan voi hajottaa kahtia, järjestää puolikkaat rekursiivisesti suuruusjärjestykseen, ja yhdistää tulokset yllä annetulla merge-ohjelmalla (joka ottaa kaksi kasvavassa järjestyksessä olevaa listaa ja palauttaa yhden, johon on yhdistetty molempien listojen elementit kasvavaan järjestykseen):
def mergesort(ls):
if len(ls) <= 1: return ls
half = len(ls) / 2
return merge(mergesort(ls[:half]), mergesort(ls[half:]))
Oikeastaan kaikki mielenkiintoinen tapahtuu merge-aliohjelmassa,
joka yhdistää kaksi järjestyksessä olevaa listaa. mergesort-ohjelma
vain jakaa listan sopiviin palasiin yhdistettäväksi.
Laskenta etenee esimerkiksi näin:
mergesort([5, 1, 3, 2, 4]) = merge(mergesort([5, 1]), mergesort([3, 2, 4])) = merge(merge(mergesort([5]), mergesort([1])), mergesort([3, 2, 4])) = merge(merge([5], [1]), mergesort([3, 2, 4])) = merge([1, 5], mergesort([3, 2, 4])) = merge([1, 5], merge(mergesort([3]), mergesort([2, 4]))) = merge([1, 5], merge([3], mergesort([2, 4]))) = merge([1, 5], merge([3], merge(mergesort([2]), mergesort([4])))) = merge([1, 5], merge([3], merge([2], [4]))) = merge([1, 5], merge([3], [2, 4])) = merge([1, 5], [2, 3, 4]) = [1, 2, 3, 4, 5]
Tällä kertaa laskennan etenemistä on vaikeampaa seurata, mutta yleinen periaate pysyy: jos mergesort pystyy järjestämään triviaalin listan ja määrittämään mielivaltaisen pitkän listan järjestämisen lyhyempien listojen järjestämisen perusteella (eli itsensä avulla rekursiivisesti), niin se väistämättä pystyy järjestämään minkä tahansa listan.
Rekursio Scheme-kielessä: http://sange.fi/~atehwa/scheme-kurssi/repetitio.html
Rekursio lambdakalkyylissa ja teoreettista pohdintaa: http://sange.fi/~atehwa/lambda-kurssi/luento5.html
(Takaisin ohjelmoinnin käsitteet -sivulle.)
Pikalinkit: