Kasutaja:HenrikTamm/Rekursiivne algoritm

Rekursiivne algoritm on probleemi lahendamise viis, kus tulemus oleneb sama probleemi väiksemate üksuste tulemustest. Programmeerimises täidab rekursiivne algoritm iseloomu poolest sama ülesannet, mida täidab tsükkel, kuid teeb seda iseennast enda keha sees välja kutsudes. Kui tsükli koodi jaoks on eraldatud tükk mälus ja selles olevate muutujate väärtusi muudetakse mälus oleva informatsiooni muutmisel, siis rekursiivse algoritmi puhul eraldatakse enesesse pöördumise korral igale alamprogrammile oma osa mälus. Läbi rekursiivsete algoritmide on võimalik defineerida lõpmatu arv kalkulatsioone lõpliku rekursiivse koodilõiguga.

Rekursiivne funktsioon erinevates programmeerimiskeeltes

Enamus programmeerimiskeeltes on võimalik rakendada rekursiivset probleemi lahendamist, kuid eksisteerib erandeid. Originaalne IBM-i poolt matemaatiliste ja teaduslike probleemide lahendamiseks loodud programmeerimiskeel FORTRAN kasutas staatilist muutujate paigutamist ning seetõttu on üks vähestest keeltest, mis ei võimalda rekursiooni. Aastaid hiljem, kui lasti välja FORTRAN 90 lisati võimalus lisada märksõna "recursive", et määrata rekursiivset lahendust. Vastupidiselt eksisteerib programmeerimiskeeli nagu näiteks Prolog, mis ei võimalda tsükli realiseerimist ja seega on igasugune tsükli töö realiseeritud läbi rekursiooni.

Näiteid

Python:

def funktsioon():
    funktsioon()

Java:

static void funktsioon(){
    funktsioon();
}

C:

void funktsioon()
{
    funktsioon();
}

R:

funktsioon <- function()
{
    funktsioon()
}

FORTRAN 90:

recursive function funktsioon() result()
    funktsioon()
end function funktsioon

Rekursiooni tüübid

Ühekordne rekursioon

Kõige tavalisem rekursiooni ülesehitus on ühekordse enda väljakutsumisega ehk ühekordne rekursioon. Ühekordne rekursioon on tihti palju efektiivsem, kui mitmekordne rekursioon ja on enamus kordadel võimalik asendada iteratiivse arvutusega. Ühekorde rekursioon jookseb lineaarselt.

Näide ühekordse rekursiooniga faktoriaali arvutamise funktsioonist:

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

Mitmekordne rekursioon

Algoritmi keha, kus toimub rohkem kui kaks enda väljakutsumist on mitmekordne rekursiooniks. Vahel on võimalik teha mitmekordset rekursiooni ümber ühekordseks. Mitmekordne rekursioon jookseb eksponentsiaalselt ehk lahendamise aja kulu ja alamprogrammide maht kasvavad eksponentsiaalselt.

Näide mitmekordse rekursiooniga kinkide jaotamise funktsioonist:

def kingijaotus(majad):
    if len(majad) == 1:
        maja = majad[0]
        print("Kink sai viidud majja ", maja)
    else:
        keskmine = len(majad) // 2
        esimene_pool = majad[:keskmine]
        teine_pool = majad[keskmine:]
        
        kingijaotus(esimene_pool)
        kingijaotus(teine_pool)

See näide kasutab binaarset sortimist/otsimist, kus iga rekursiooni astme korral jagatakse loend pooleks, et jõuda otsitud tulemuseni.

Kaudne rekursioon

Kui funktsioon kutsub ennast rekursiivselt välja enda keha sees siis see on otsene rekursioon. Nii ühekordne kui ka mitmekordne rekursioon kuuluvad otsese rekursiooni alla. Kui aga funktsioon kutsub välja teise funktsiooni, mis kutsub välja algse funktsiooni, on tegemist kaudse rekursiooniga ehk funktsioonid on defineeritud üksteise kaudu. Näiteks, kui f kutsub välja g, mis omakorda kutsub välja f, siis toimub kaudne rekursioon funktsioonis f. Samuti on võimalik luua kaudset rekursiooni kolme või rohkema funktsiooniga. Näiteks, esimene funktsioon kutsub välja teise, mis kutsub välja kolmanda, mis lõpuks kutsub välja jälle esimese funktsiooni.

Näide kaudsest rekursioonist:

def ping(i):
    if i>0:
        return pong(i-1)
    else:
        return "0"
def pong(i):
    if i>0:
        return ping(i-1)
    else:
        return "1"

Struktuurne ja generatiivne rekursioon

Struktuurse ja generatiivse rekursiooni vahe seisneb selles, kus rekursiivne protsess saab andmed, mille põhjal ta töötab ja kuidas ta neid andmeid töötleb ning nende pähjal tulemuseni jõuab.

Struktuurne rekursioon

Struktuurse rekursiooni korral on iga rekursiooni sammu argumendiks osa originaalsest argumendist, mis kuulub ka samasse klassi kuhu kuulub originaalne argument. Kui struktuurse rekursioon töötleb lõplikut andmestruktuuri, siis saame struktuurse induktsiooniga näidata, et rekursioon on lõplik - kuna iga rekursiooni sammuga vähenevad sisendi andmed, siis üks hetk jõuab rekursioon baasini. Seega struktuurne rekursioon on siis, kui rekursioon algab lõplikuna ja iga sammu korral väheneb. Struktuurse rekursioon on näiteks binaarse puu loomine või puu läbi otsimine. Kui võtta suvalist naturaalarvude hulka kui andmestruktuurina, siis on ka faktoriaali arvutamise rekursiivne funktsioon struktuurne rekursioon.

Generatiivne rekursioon

Generatiivse rekursiooni korral ei ole iga rekursiooni sammu korral sisendiks alati väiksem osa originaalist, vaid pigem luuakse uus andme üksus, mida töödeldakse. Kuna seega puudub ka kindel baas, ei ole generatiivse rekursiooni lõpetamine tihtipeale kerge ning ilma kindla baasi astme tingimuseta on lõpmatut tsüklit raske vältida. Seega ebakindlate andmeüksuste korral oleneb rekursiooni lõplikus vaid funktsioonist enesest.

Näiteid rekursiivsetest funktsioonidest

Hanoi tornid

Hanoi tornid on populaarne matemaatiline mõistatus, mis kujutab rekursiooni. Mõistatuses on kolm erinevat võimalikku torin , kus saavad suvaline arv erineva diameetriga silindreid asuda üksteise peal vaid nii, et ükski suurema diameetriga silinder ei ole teise väiksema silindri peal. Ülesanne on ühest tornist kus asuvad kõik silindrid paigutada kõik silindrid ühekaupa samasuguses kasvavas järjekorras teise torni. Kasutades rekursiooni saame arvutada minimaalse arvu käike, millega saab lahendada ülesanne suvalise arvu silindritega.

Minimaalset arvu arvutav rekursiivne funktsioon Pythonis:

def hanoi(n):
    if n == 1:
        return 1 
    else: 
        return 2 * hanoi(n - 1) + 1

Rekursiivne puu

Näide koodilõigus esitatud koodist saadud puust.

Rekursiivne puu on üks tavalisemaid viise, kuidas mitmekordse rekursiooniga probleemidele lähenetakse. Tihtipeale on rekursiivse puu idee pigem lähenemisviis, kui reaalne puu.

Pythonis kirjutatud rekursiivne puu, visualiseeritud mooduliga "turtle":

def puu(haru_arv, pikkus):
    if haru_arv != 0:
        koht = pos()
        suund = heading()
        fd(pikkus)
        lt(30)
        puu(haru_arv - 1, pikkus // 2)
        puu(haru_arv - 1, pikkus // 2)
        puu(haru_arv - 1, pikkus // 2)
        puu(haru_arv - 1, pikkus // 2)
        setpos(koht)
        seth(suund)
        rt(30)