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 | redigeeri 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 | redigeeri lähteteksti]

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

Lineaarne[muuda | redigeeri 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 | redigeeri lähteteksti]

Puurekursiooni puhul toimub ühes funktsioonis rohkem kui üks sama funktsiooni väljakutset. Nende arv ei ole piiratud aga peab arvestama arvutamisele kuluvat aega. 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 | redigeeri 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 | redigeeri 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 | redigeeri lähteteksti]

Tavalises rekursioonis toimub iga väljakutse korral ülesande lahendamine järkjä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 | redigeeri 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 | redigeeri lähteteksti]

Rekursiivne faktoriaal[muuda | redigeeri 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 seda leiab? Tehes selle funktsiooni väljakutse print(faktoriaal(5)), algab järgnev 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 | redigeeri 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 mõelge konteinerist kui kalkulaatorist mida funktsioon endaga kaasas kannab. Enne uue väljakutse peale minemist lüüakse kalkulaatorisse uued numbrid sisse ja leitakse juba vastus ära. 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 | redigeeri lähteteksti]

13. sajandi alguses kasutas Leonardo Fibonacci seda arvude jada kirjeldamaks jäneste populatsiooni kasvu. Selles jadas on iga järgnev liige kahe eelnevas summa ning 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 5-ndat elementi, mis on tõesti 3.

Vastastikune rekursioon[muuda | redigeeri 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 järgnevalt ainult mõnede väljakutsete 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   
boolean[12] tüüpi True or False väärtusi palju ning mõne üksiku lisakoodirea kirjutamine nende väärtuste kasutamiseks on kerge.

Fraktalid[muuda | redigeeri 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 viidete alt.

Arvuti looming[muuda | redigeeri lähteteksti]

Fraktalite joonistamiseks on loodud palju erinevat tarkvara. On nii vabavaralisi kui kommertslikke. Google otsingusse "fractal generator" või "best fractal program" sisse toksides leiab juba esimeselt leheküljelt suure valiku neist.

Looduse ilu[muuda | redigeeri lähteteksti]

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

Rekursioon humanitaarteadustes[muuda | redigeeri lähteteksti]

Kõnekeeles[muuda | redigeeri 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 | redigeeri 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 | redigeeri lähteteksti]

1981. aastal lasi bänd nimega 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 ainult 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-minooris aga tundub et lõpetab D-minooris. Selle lõpp ühendub sujuvalt algusega ja kogu protsess algab otsast peale aga seekord D-minooris ja lõppeb E-minooris. Peale kuut sellist modulatsiooni on pala tagasi C-minoori alguses aga oktaavi võrra kõrgem ja kogu protsess saab otsast peale alata.

Rekursiivne huumor[muuda | redigeeri lähteteksti]

Viited[muuda | redigeeri lähteteksti]

Kasutatud kirjandus[muuda | redigeeri lähteteksti]

  • Learning with Python 3
  • Recursion in Phonology

Kasulikud lingid[muuda | redigeeri lähteteksti]