Rekursioon

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

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 viimast üldjuhul võimsamaks. Reeglikohaselt saab iga iteratsiooni ehitada rekursiivseks, aga rekursiivse funktsiooni kirjutamisel iteraktiivseks on vaja magasini 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üübid

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

Lineaarne

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 rekursioon

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.

Vastastikune

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.

Sisestatud

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

Tavalises rekursioonis lahendatakse ülesanne iga väljakutse korral järk-järgult nõrgima variandini, seejärel saadetakse tulemused tagasi ülespoole ja alles siis summeeritakse. Sabarekursioonis tehakse iga astme korral arvutusi 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 limiit

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 Pythonis

Rekursiivne faktoriaal

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

Siin arvutatakse matemaatikast tuntud faktoriaali. Arutluse 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 faktoriaal

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 arvud

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 rekursioon

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.

Fraktalid

 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 looming

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 ilu

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

• 
• 
• 
• 
• 

Rekursioon humanitaarteadustes

Kõnekeeles

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

Kunstis

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.

Muusikas

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 ka

• autoreproduktsioon
• iteratsioon

Välislingid

• Rekursiooni vormid
• Vastastikune rekursioon erinevates programmeerimiskeeltes
• Näide rekursiooni ja selle erijuhu summadest
• Rekursioonist kunstis ja elus