Rekursioon

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

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

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

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 funktsioon, mida ei nimetata primitiivseks rekursiooniks nagu eelnevaid vorme.

Erijuht: sabarekursioon

Tavalises rekursioonis toimub iga väljakutse korral ülesande lahendamine järk-järgult nõrgima 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, 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

See termin on programmeerimiskeele interpretaatori spetsiifiline. Viimastel on üldiselt paika pandud mingi limiit, kui kaugele rekursioon võib minna. Pythoni interpretaator IDLE  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.

Rekursiivne faktoriaal

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

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

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

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:
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 tüüpi True or False väärtusi palju ning mõne üksiku lisakoodirea kirjutamine nende väärtuste kasutamiseks on kerge.

Arvuti looming

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

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

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 lausest sama struktuuriga. Ei eksisteeri pikimat lauset, kuid 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 kakaopurgi järgi. Meie idanaabrite matrjoška nukud on vast kõigile teada-kuuldud. Suurima nuku sees on väiksem nukk, selle sees veel väiksem ja nii edasi.

Muusikas

1981. aastal andis bänd The Look  välja singli "I am the beat". Mis teeb selle vinüülplaadile 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.
Klassikalisest muusikast on tuntud näide Johann Sebastian Bachi "Canon per Tonos" ooperist "Das Musikalische Opfer", mida kutsutakse lõputult tõusvaks kaanoniks. Teatud hetkest see pala moduleerib nii, et läheb kõrgemaks ühe tooni võrra iga korduse kohta. Kaanon tervikuna on C-mollis, aga jääb mulje, 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.