Rekursioon

Allikas: Vikipeedia

Rekursioon on mingi objekti kordamine ennastkopeerival teel. Olles valdavalt arvutiteaduses ja matemaatikas kasutusel olev termin, on sel juuri ka humanitaarteadustes.

Screenshot Recursion via vlc.png

Rekursiooni olemus[muuda | muuda lähteteksti]

Rekursioon on olukord, kus näiteks arvutiprogrammis defineeritud funktsioon kutsub iseennast välja, et lahendada funktsioonile antud probleemi kergem variant. Rekursiooni astmeid võib olla lõputult palju aga korrektse rekursiivse funktsiooni puhul on alati defineeritud baasjuhtum, mille korral rekursiooni edasikaevumine lihtsama variandi poole peatub. Kui baasjuhtumit ei defineerita, siis on rekursioon lõputu ja 99% juhtudest toob kaasa programmi kokkujooksmise välja arvatud spetsiifiliste programmeerimiskeelte puhul, nagu Fortran, Ada [1] ja Ruby [2], kus see on lubatud.

Rekursioon on võrreldav programmeerimisest tuntud iteratsiooni ehk for[3] ja while[4] tsüklitega. Kuigi võib tunduda lihtsam defineerida iteratsioone kui kasutada rekursiivset funktsiooni, peetakse viimast üldjuhul võimsamaks. Rusikareegel on, et iga iteratsiooni saab ehitada rekursiivseks aga rekursiivse funktsiooni kirjutamiseks iteraktiivseks on vaja magasini[5] ehk lisafunktsiooni väärtuste hoidmiseks. See toob omakorda kaasa koodiridade kasvu.

Reaalses elus saab rekursiooni näha näiteks veebikaamera pööramisel kuvarile, kui see töötab ja pilt on kuvatud ekraanile. Teine näide on kahe peegli pööramine teineteise vastu ja ise olles kahe peegli vahel jälgides ühte neist. Kui peeglid on eri suurusega, siis võib natuke aega minna, enne kui leida õige [6] rekursiooni nägemiseks.

Rekursiooni tüübid[muuda | muuda lähteteksti]

Olenevalt viisist, kuidas funktsioon ja selle nõrgema(te) astme(te) väljakutse toimub, eristatakse järgmisi rekursiooni vorme.

Lineaarne[muuda | muuda lähteteksti]

Funktsiooni kehas kutsutakse funktsiooni ennast välja maksimaalselt ainult ühe korra. Seda võib ette kujutada kui naturaalarvude loendamist kasvavalt, kus väljakutseks on n+1 ja ekraanile prinditakse enne väljakutset n ise.

Puurekursioon, binaarne rekursioon[muuda | muuda lähteteksti]

Puurekursiooni puhul toimub ühes funktsioonis rohkem kui üks sama funktsiooni väljakutset. Nende arv ei ole piiratud, aga arvesse tuleb võtta ka arvutamiseks kuluv aeg. Väljakutsete ja tasemete suurendamisel on programmi töö ajakulu hüpe eksponentsiaalne. Binaarne rekursioon on puurekursiooni lihtsaim vorm, kus funktsioon kutsub ennast ainult 2 korda välja. Fibonacci arvude arvutamine on viimase kohta väga levinud näide.

Vastastikune[muuda | muuda lähteteksti]

Selle vormi korral on defineeritud kaks erinevat funktsiooni. Väljakutse toimub viisil, kus esimene kutsub teist ja teine kutsub esimest. Iseennast kumbki funktsioon välja ei kutsu. Rekursiivseks kutsutakse seda vormi sellepärast, et esimesele funktsioonile antud argument kandub üle teisele ja vastupidi. Olenevalt ülesandest toimub argumendi edasiandmine kas kahanevalt või kasvavalt.

Sisestatud[muuda | muuda lähteteksti]

See on keeruline ja arvutusmahukas variant. Siin on funktsiooni iseenda väljakutse üheks või enamaks argumendiks funktsioon ise, kus alles toimub vastava argumendi kahanemine. Ka siin on ajakulu kasv argumentide suurendamisega eksponentsiaalne. Levinud näide selle kohta on Ackermanni[7] funktsioon, mida ei nimetata primitiivseks rekursiooniks nagu eelnevaid vorme.

Erijuht: sabarekursioon[muuda | muuda lähteteksti]

Tavalises rekursioonis toimub iga väljakutse korral ülesande lahendamine järk-järgult nõrgeima variandini ja siis tulemuste saatmine tagasi ülespoole ning alles siis summeerimine. Sabarekursioonis toimub iga astme korral arvutuste tegemine enne järgnevat rekursiivset väljakutset. See tähendab ühe lisaargumendi lisamist funktsiooni päisesse[8], mis käitub kui konteiner eelnevate arvutuste summeerimiseks. Sabarekursioon on koodiridade poolest pikem aga programmi interpretaatorile kergem käsitleda, sest ei ole vaja mälus hoida lahtisena igat rekursiooni astet, mis ootavad lahendusi madalamatelt juhtudelt.

Rekursiooni limiit[muuda | muuda lähteteksti]

See termin on programmeerimiskeele interpretaatori spetsiifiline[9]. Viimastel on üldiselt paika pandud mingi limiit, kui kaugele rekursioon võib minna. Pythoni interpretaator IDLE [10] lubab vaikeseadena 1000 astet. Seda saab lisakoodiridade abil muuta vastava programmi nõuetele vastavaks. Kui näiteks tahetakse rekursiivselt ükshaaval lugeda ja ekraanile printida naturaalarve 1002-st 1-ni, siis tuleb eelsätestatud limiiti tõsta.

Näited Pythonis[muuda | muuda lähteteksti]

Rekursiivne faktoriaal[muuda | muuda lähteteksti]

def faktoriaal(n):
    if n == 0:
         return 1
    else:
         return n * faktoriaal(n-1)

Mis siin toimub? Arvutatakse matemaatikast tuntud faktoriaali. Võtame arutuluse alla faktoriaali 5-st, mis tähendab 5! = 1*2*3*4*5 = 120. Kuidas programm selle leiab? Tehes selle funktsiooni väljakutse print(faktoriaal(5)), algab järgmine protsess:

faktoriaal(5)
5*faktoriaal(4)
5*(4*faktoriaal(3))
5*(4*(3*faktoriaal(2)))
5*(4*(3*(2*faktoriaal(1))))
5*(4*(3*(2*(1*faktoriaal(0)))))
5*(4*(3*(2*(1*(1)))))
120

Kõik astmed, mis siin läbi käiakse, ootavad lahendust oma alamastmelt. Kui rekursioon jõuab oma baasjuhuni, milleks on n == 0, siis lisatakse kogu korrutisse lihtsalt 1, sest matemaatiliselt on defineeritud 0! = 1. Lõpuks prinditakse ekraanile 120.

Sabarekursiivne faktoriaal[muuda | muuda lähteteksti]

def sabafaktoriaal(n,konteiner):
    if n == 0:
        return konteiner
    else:
        return sabafaktoriaal(n-1,konteiner*n)

Tehes funktsiooni väljakutse print(sabafaktoriaal(5,1)) algab järgmine protsess:

NB! Konteineri algväärtuseks valime 1, sest tegu on korrutamisega.
Teadagi 0 * mistahes arv = 0. Seega antud funkts. nõuab 1-te.
Summa leidmise korral tuleks loomulikult konteiner panna võrduma 0-ga.
sabafaktoriaal(5,1)
sabafaktoriaal(4,5)
sabafaktoriaal(3,20)
sabafaktoriaal(2,60)
sabafaktoriaal(1,120)
120

Nagu näha, toimuvad kõik arvutused enne uut rekursiivset väljakutset. See ei pruugi kohe arusaadav olla, aga kujutlegem konteinerit kui kalkulaatorit, mida funktsioon endaga kaasas kannab. Enne uue väljakutse peale minemist lüüakse kalkulaatorisse uued numbrid sisse ja leitakse juba vastus. Iga uue astme peal lihtsalt lisatakse tegur juba olemasolevale vastusele. Lõpus kui n väärtus jõuab 0-ni, siis tagastatakse konteiner ja ekraanile prinditakse 120.

Fibonacci arvud[muuda | muuda lähteteksti]

13. sajandi alguses kasutas Leonardo Fibonacci seda arvude jada kirjeldamaks jäneste populatsiooni kasvu. Selles jadas on iga järgmine liige kahe eelneva summa ja algab nullist. Seega on jada järgmine: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

def leiaFib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return leiaFib(n-1) + leiaFib(n-2)

leiaFib(4) tagastab vastuseks 3

Siin on tegemist eelpool mainitud puurekursiooniga. Puuoksad saavad ilmsiks juba leiaFib(4) väljakutsel, seega pole mõtet hakata leidma jada kaugemaid arve funktsiooni töö demonstreerimiseks.

NB! Normaalse loendamise loogika ütleb, et Fibonacci jada neljas element peaks olema 2. Kuna arvutiteadustes algab 
paljude asjade loendamine 0-st, siis leiaFib(4) otsib tegelikult jada viiendat elementi, mis on tõesti 3.

Vastastikune rekursioon[muuda | muuda lähteteksti]

def paaris(x):
    if x == 0: return "Õige"
    else: return paaritu(x-1)

def paaritu(x):
    if x == 0: return "Vale"
    else: return paaris(x-1)

Funktsioon paaris kutsub välja funktsiooni paaritu ja vastupidi niikaua kuni jõutakse baasjuhuni. Kuna mõlema funktsiooni baasjuhu tingimus on samasugune, siis tagastatav string[11] ehk sõne sõltub sellest, kumb funktsioon enne baasjuhuni jõuab. Kuna funktsiooni töökäik on lineaarne ja seega triviaalne, siis on siin esitatud ainult mõne väljakutse vastused:

print(paaris(4)) tagastab: Õige
print(paaris(5)) tagastab: Vale
print(paaritu(4)) tagastab: Vale
print(paaritu(5)) tagastab: Õige
Esmapilgul tundub imelik, et miks tagastatavad väärtused ei võiks olla "Paarisarv" ja "Paaritu arv." Siis oleks kohe õigel kujul vastus olemas ning poleks vaja tagastatavat       
stringi edasi töödelda. See viiks aga kohati valede tulemusteni olenevalt sellest kummale funktsioonile uuritav arv enne antakse. Pealegi kasutatakse arvutiteadustes   
kahendmuutuja[12] tüüpi True or False väärtusi palju ning mõne üksiku lisakoodirea kirjutamine nende väärtuste kasutamiseks on kerge.

Fraktalid[muuda | muuda lähteteksti]

Next.svg Pikemalt artiklis Fraktal

Neid kui kõige elegantseimad visuaalse rekursiooni esitamise viise kasutatakse arvutiteadustes palju. Kuigi neil ei ole suurt praktilist väärtust, on neid siiski väga ilus vaadata. Samuti annavad nad aimu erisuguste rekursioonide käitumisest ning kui muidu sellest teemast matemaatiliselt aru ei saa, siis pildid ütlevad kohe mis protsessiga on tegu.

Fraktalid käituvad nagu rekursioon ikka, neil on oma baasjuhtum ja tase, kuid argument mida kasutatakse joonistuse tegemiseks väheneb(kasvab) iga taseme vähenemise(kasvu)ga. See tähendab seda et iga alam(ülem)taseme väljakutse joonistus on erineva suurusega, kuid see on osa suurest pildist. Siinkohal ilusate ja värviliste fraktalite koodi arutamine on keeruline, piirdume ainult silmailuga ja kellel huvi, võib leida rohkem infot artikli viidete abil.

Arvuti looming[muuda | muuda lähteteksti]

Fraktalite joonistamiseks on loodud palju erinevat tarkvara. On nii vabavaralisi kui ka kommertslikke. Google'i otsingusse otsiväljendi "fractal generator" või "best fractal program" sisestamise järel võib leida juba esimeselt leheküljelt suure valiku neist.

Looduse ilu[muuda | muuda lähteteksti]

Eluslooduses leidub palju fraktalitaolisi struktuure, sealhulgas kolmemõõtmelisi.

Rekursioon humanitaarteadustes[muuda | muuda lähteteksti]

Kõnekeeles[muuda | muuda lähteteksti]

[ta näeb und]
[ta näeb und, et [ta näeb und]]
[ta näeb und, et [ta näeb und, et [ta näeb und]]]
jne.

Igat lauset võib jätkata lõputult tehes selle osaks suuremast lausest sama struktuuriga. Ei eksisteeri pikeimat lauset, kuid selliseid lauseid ei moodustata ainult samadest sõnadest, küll aga peab sõnade tähendus jääma samaks.

Kunstis[muuda | muuda lähteteksti]

Siin on üheks tuntumaks näiteks "Droste effect", mis sai oma nime ühest hollandi kakaopurgi järgi. Meie idanaabrite matrjoška nukud[13] on vast kõigile teada-kuuldud. Suurima nuku sees on väiksem nukk, selle sees veel väiksem ja nii edasi.

Muusikas[muuda | muuda lähteteksti]

1981. aastal lasi bänd The Look [14] välja singli "I am the beat". Mis teeb selle vinüülplaadile[15] kirjutatud loo huvitavaks, on selle lõputus. Vinüülplaadi viimane rida on tehtud ringjooneks ja see mängib trummide osa, mis on pandud täpselt vastavusse plaadimängija 45 plaadipöördega minutis. Sellepärast lugu muudkui kestab ja kestab.

Klassikaliset muusikast on tuntud näide Johann Sebastian Bachi "Canon per Tonos" ooperist "Das Musikalische Opfer"[16], mida kutsutakse lõputult tõusvaks kaanoniks. Teatud hetkest see pala moduleerib[17] nii, et läheb kõrgemaks ühe tooni võrra iga korduse kohta. Kaanon tervikuna on C-mollis, aga jääb mulje, et et lõpetab D-mollis. Selle lõpp ühendub sujuvalt algusega ja kogu protsess algab otsast peale, aga seekord D-mollis ja lõpeb E-mollis. Pärast kuut sellist modulatsiooni on pala tagasi C-molli alguses, aga oktaavi võrra kõrgem ja kogu protsess saab otsast peale alata.

Rekursiivne huumor[muuda | muuda lähteteksti]

Viited[muuda | muuda lähteteksti]

Kasutatud kirjandus[muuda | muuda lähteteksti]

  • Learning with Python 3
  • Recursion in Phonology

Kasulikud lingid[muuda | muuda lähteteksti]