Rekursioon

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

Screenshot Recursion via vlc.png

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 peatub rekursioon lihtsama variandi poole. Kui baasjuhtumit ei defineerita, siis on rekursioon lõputu ja enamikul juhtudel jookseb programm kokku, välja arvatud spetsiifiliste programmeerimiskeelte puhul nagu Fortran, Ada ja Ruby, kus see on lubatud.

Rekursioon on võrreldav programmeerimisest tuntud iteratsiooni ehk for- ja while- tsüklitega. Kuigi võib tunduda lihtsam defineerida iteratsioone, kui kasutada rekursiivset funktsiooni, peetakse[kes?] viimast üldjuhul võimsamaks. Reeglikohaselt saab iga iteratsiooni ehitada rekursiivseks, aga rekursiivse funktsiooni kirjutamisel iteraktiivseks on vaja magasini[1] ehk lisafunktsiooni väärtuste hoidmiseks. Seetõttu tuleb koodiridu juurde.

Reaalses elus saab rekursiooni näha näiteks veebikaamera pööramisel kuvarile, millel on pilt. Samuti võib kaks peeglit teineteise vastu pöörata ning peeglite vahel neist ühte vaadelda. Kui peeglid on eri suurusega, siis võib õige rekursiooni nägemine natuke aega võtta.

Rekursiooni tüübidRedigeeri

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

LineaarneRedigeeri

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

Puurekursioon, binaarne rekursioonRedigeeri

Puurekursiooni puhul toimub ühes funktsioonis rohkem kui üks sama funktsiooni väljakutse. Nende arv ei ole piiratud, aga arvesse tuleb võtta ka arvutamiseks kuluvat aega. Väljakutsete ja tasemete suurendamisel on programmi töö ajakulu eksponentsiaalne.

Binaarne rekursioon on puurekursiooni lihtsaim vorm, kus funktsioon kutsub ennast ainult kaks korda välja. Fibonacci jada arvutamine on selle kohta väga levinud näide.

VastastikuneRedigeeri

Selle vormi korral on defineeritud kaks funktsiooni. Väljakutse toimub viisil, kus esimene kutsub teist ja teine kutsub esimest. Iseennast kumbki funktsioon välja ei kutsu. Seda vormi kutsutakse rekursiivseks, kuna esimesele funktsioonile antud argument kandub üle teisele ja vastupidi. Olenevalt ülesandest antakse argument edasi kas kahanevalt või kasvavalt.

SisestatudRedigeeri

See on keeruline ja arvutusmahukas variant. Siin on funktsiooni väljakutse üheks või enamaks argumendiks funktsioon ise, kus vastav argument kahaneb. Ka siin on ajakulu kasv argumentide suurendamisega eksponentsiaalne. Levinud näide selle kohta on Ackermanni funktsioon, mida ei nimetata primitiivseks rekursiooniks nagu eelnevaid vorme.

Erijuht: sabarekursioonRedigeeri

Tavalises rekursioonis lahendatakse ülesanne iga väljakutse korral järk-järgult nõrgima variandini, seejärel tulemuste saatmine tagasi ülespoole ja alles siis summeerimine. Sabarekursioonis tehakse iga astme korral arvutuste tegemine enne järgnevat rekursiivset väljakutset. See tähendab ühe lisaargumendi lisamist funktsiooni päisesse, mis käitub kui konteiner eelnevate arvutuste summeerimiseks. Sabarekursioon on koodiridade poolest pikem, kuid programmi interpretaatoril on seda kergem käsitleda, sest mälus ei ole vaja lahtisena hoida igat rekursiooni astet, mis ootab lahendust madalamatelt juhtudelt.

Rekursiooni limiitRedigeeri

See termin on programmeerimiskeele interpretaatorist olenev. Interpretaatoritel on üldiselt määratud limiit, kui kaugele rekursioon võib minna. Pythoni interpretaator IDLE lubab vaikeseadena 1000 astet. Seda saab lisakoodiridade abil muuta programmi nõuetele vastavaks. Kui näiteks tahetakse rekursiivselt ükshaaval lugeda ja ekraanile printida naturaalarve 1002-st 1-ni, siis tuleb limiiti tõsta.

Näited PythonisRedigeeri

Rekursiivne faktoriaalRedigeeri

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

Siin arvutatakse matemaatikast tuntud faktoriaali. Arutuluse alla on võetud faktoriaal 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 kuvatakse ekraanile 120.

Sabarekursiivne faktoriaalRedigeeri

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äärtus peab olema 1, sest tegu on korrutamisega.
Teadagi 0 * mistahes arv = 0. Seega antud funktsioon nõuab numbrit 1.
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 on arusaadavam, kui mõelda konteinerist kui kalkulaatorist, mida funktsioon endaga kaasas kannab. Enne uut väljakutset sisestatakse kalkulaatorisse uued arvud ja leitakse vastus. Iga uue astme peal lisatakse tegur juba olemasolevale vastusele. Lõpuks, kui n-i väärtus jõuab 0-ni, tagastatakse konteiner ja ekraanile kuvatakse 120.

Fibonacci arvudRedigeeri

13. sajandi alguses kasutas Leonardo Fibonacci seda arvude jada kirjeldamaks jäneste populatsiooni kasvu. See on jada, kus kaks esimest liiget on 0 ja 1 ning alates kolmandast liikmest on iga järgmine liige võrdne kahe eelneva liikme summaga: 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)

 

Siin on tegemist eespool 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 arvutiteaduses algab loendamine sageli 0-st, siis leiaFib(4) otsib tegelikult jada viiendat elementi, mis on 3.

Vastastikune rekursioonRedigeeri

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 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

Võib tekkida küsimus, miks tagastatavad väärtused ei võiks olla paaris ja paaritu. Sellisel juhul oleks vastus kohe õigel kujul olemas ning poleks vaja tagastatavat sõnet edasi töödelda. See viiks aga kohati valede tulemusteni olenevalt sellest, kummale funktsioonile uuritav arv enne antakse. Pealegi kasutatakse arvutiteaduses kahendmuutuja tüüpi True or False väärtusi palju ning mõne üksiku lisakoodirea kirjutamine nende väärtuste kasutamiseks on kerge.

FraktalidRedigeeri

  Pikemalt artiklis Fraktal

Neid kui kõige elegantsemaid visuaalse rekursiooni esitamise viise kasutatakse arvutiteaduses palju. Kuigi neil ei ole suurt praktilist väärtust, on neid siiski väga ilus vaadata. Samuti annavad nad aimu erisuguste rekursioonide käitumisest.

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/kasvuga. See tähendab, et iga alam- või ülemtaseme väljakutse joonistus on erineva suurusega, olles samas osa suurest pildist.

Arvuti loomingRedigeeri

Fraktalite joonistamiseks on loodud palju vabavaralist ja kommertslikku tarkvara, mis on leitav Google'i otsingusse otsiväljendi fractal generator või best fractal program sisestamisel.

Looduse iluRedigeeri

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

Rekursioon humanitaarteadustesRedigeeri

KõnekeelesRedigeeri

[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 sama struktuuriga lausest. Selliseid lauseid ei moodustata ainult samadest sõnadest, küll aga peab sõnade tähendus jääma samaks.

KunstisRedigeeri

Kunstis on üks tuntumaid näiteid Droste effect, mis sai nime ühe Hollandi kakaobrändi järgi. Tuntud on ka meie idanaabrite matrjoška, kus suurema nuku sees on väiksem nukk, selle sees veel väiksem jne.

MuusikasRedigeeri

1981. aastal andis bänd The Look välja singli "I am the beat". Vinüülplaadile kirjutatud loo teeb huvitavaks selle lõputu kestvus. Plaadi viimane rida on kujundatud ringjooneks ja see mängib trummide osa, mis on viidud vastavusse plaadimängija 45 plaadipöördega minutis. Sellepärast lugu muudkui kestab ja kestab.

Klassikalisest muusikast on tuntud näide Johann Sebastian Bachi "Canon a 2 per Tonos" ooperist "Das Musikalische Opfer", mida kutsutakse lõputult tõusvaks kaanoniks. Teatud hetkest moduleerib see pala nii, et läheb kõrgemaks ühe tooni võrra iga korduse kohta. Kaanon tervikuna on C-mollis, aga lõpeb D-mollis. Selle lõpp ühendub sujuvalt algusega ning kogu protsess algab otsast peale 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 algab otsast peale.

Vaata kaRedigeeri

ViitedRedigeeri

VälislingidRedigeeri