Rekursioon

Programmeerimises nimetatakse rekursiooniks seda, kui funktsioon kutsub välja iseennast. Järgnevalt on toodud kaks näidet rekursiooni kasutamise kohta:

• Kanooniline näide: faktoriaali arvutamine - sobib lugemiseks neile, kes on vähe matemaatikalembesed,
• Praktiline näide: Puukujulise menüü kuvamine andmebaasist

Kanooniline näide: faktoriaali arvutamine

Sageli tutvustatakse rekursiooni faktoriaali arvutamise näitel. Arvu n faktoriaal (n!) on defineeritud järgnevalt:

n! = 1 · 2 · 3 · ... · n

Näiteks arvu 3 faktoriaal on:

3! = 1 · 2 · 3 = 6

Ja arvu 4 faktoriaal on:

4! = 1 · 2 · 3 · 4 = 24

Kui me sedasi nende faktoriaalide arvutamist jätkame, siis märkame, et järgmise arvu faktoriaali saame kergesti kätte, kui teame talle eelneva arvu faktoriaali. Näiteks arvu 5 faktoriaali arvutamine muutub tublisti lihtsamaks kui tema arvu 4 faktoriaali:

5! = 4! · 5 = 120

Seega võime nüüd defineerida, et et arvu n faktoriaal on arvu n enda ja talle eelneva arvu faktoriaali korrutis (välja arvatud see juhtum, et arvu 1 faktoriaaliks on alati 1). Ehk matemaatiliselt väljendudes:

n! = 1, kui n = 1

n! = (n - 1)! · n, kui n > 1

Siin definitsioonis aga ongi meil juba rekursioon - defineerimaks faktoriaali olemust, kasutame me faktoriaali ennast.

Selle matemaatilise definitsiooni põhjal saame me nüüd kirjutada faktoriaali arvutava funktsiooni mõnes programmeerimiskeeles:

 function faktoriaal(n) {
     if (n == 1)
         return 1;
     else
         return faktoriaal(n-1) * n;
  }

Selleks, et saada aimu, mida rekursiooniga ka praktikas peale hakata (eeldades, et faktoriaalide arvutamine pole su igapäevaleib), loe edase ka järgmist näidet.

Praktiline näide: Puukujulise menüü kuvamine andmebaasist

Olgu meil üks aiasaadusi vahendav veebileht, millel on selline puukujuline ülesehitus:

• Kaubad
  • Juurviljad
    • Porgand
    • Peet
    • Kaalikas
  • Puuviljad
    • Õun
    • Pirn
• Müügipunktid
  • Tallinnas
  • Tartus
  • Pärnus

Mõistagi on kõik need andmed salvestatud andmebaasi tabelisse:

id	nimi	parent_id
1	Kaubad	0
2	Juurviljad	1
3	Porgand	2
4	Peet	2
5	Kaalikas	2
6	Puuviljad	1
7	Õun	6
8	Pirn	6
9	Müügipunktid	0
10	Tallinnas	9
11	Tartus	9
12	Pärnus	9

See on kõige levinum ja lihtsam meetod puukujuliste andmete andmebaasi salvestamiseks ning enamasti sellisest lihtsast struktuurist ka piisab.

Nagu näha, siis on lisaks väljadele id ja nimi ka väli parent_id, mis viitab selle rea id-le mille alla rida kuulub. Näiteks Pirni parent_id on 6, seega kuulub ta Puuviljade kategooriasse, mille id-ks on 6. Samuti on siit selgelt näha, et Puuviljade alla kuuluvad veel ka õun ja pirn, mille parent_id on samuti 6. Puuviljade parent_id on aga 1, mistõttu puuviljad käivad omakorda Kaupade alla. Kaupade parent_id on aga 0, mis tähendab, et tegemist on kõige ülemise taseme kategooriaga, mis enam millegi alla ei kuulu.

Eelnevalt esitatud küsimusi saab lihtsalt esitada ka SQL-is. Näiteks võime küsida, mis asjad kuuluvad Puuviljade (id = 6) kategooriasse:

 SELECT * FROM menyy WHERE parent_id = 6;

Ning andmebaas vastab meile:

id	nimi	parent_id
7	Õun	6
8	Pirn	6

Või siis, et kuhu kuuluvad Puuviljad (parent_id = 1) ise:

 SELECT * FROM menyy WHERE id = 1;

Ja saame vastuseks:

id	nimi	parent_id
1	Kaubad	0

Nojah, sellised päringud on muidugi lihtsad, kuid kuidas saaksime kogu selle tabeli ilusasti puukujuliselt väljastada. Alustame kõigepealt sellest, et kirjutame endale väikese abifunktsiooni, mis tagastab meile massiivi menüüelementidega, millel on sama parent_id:

function get_children($parent_id) {
    $r = mysql_query("SELECT * FROM menyy WHERE parent_id = $parent_id");
    $children = array();
    while ($row = mysql_fetch_array($r)) {
        $children[] = $row;
    }
    return $children[];
}

Nüüd on kõik meie järgnev vaev juba tublisti lihtsustatud. Kõigepealt väljastame kõige kõrgema tasandi kategooriad - see peaks olema lihtne. On meil ju teada, et kõigi ülemisel tasandil olevate asjade parent_id on alati 0. Seega saame kirjutada järgmise PHP funktsiooni:

function print_menu() {
    foreach (get_children(0) as $child) {
        echo $child["nimi"]."\n";
    }
}

Vahva. Nüüd väljastame ka järgmise tasandi menüüelemendid. Kusjuures nendele alamelementidele prindime ette väikese tühiku:

function print_menu() {
    foreach (get_children(0) as $child) {
        echo $child["nimi"]."\n";
        foreach (get_children($child["id"]) as $child2) {
            echo " ".$child2["nimi"]."\n";
        }
    }
}

Noh, ja nüüd ka kolmas tasand:

function print_menu() {
    foreach (get_children(0) as $child) {
        echo $child["nimi"]."\n";
        foreach (get_children($child["id"]) as $child2) {
            echo " ".$child2["nimi"]."\n";
            foreach (get_children($child2["id"]) as $child3) {
                echo "  ".$child3["nimi"]."\n";
            }
        }
    }
}

Kuna aga meie menüükesel ongi vaid kolm tasandit, siis ongi valmis!

Aga kui me ei tea ette kui palju meie menüüs neid tasemeid on? Mingi tuhandetasemelise menüü jaoks sellise koodi kirjutamine oleks juba ääretult tüütu. Lisaks poleks see kood just eriti ilus. Õigupoolest pole see juba praegu seda. Seal on sees mingid tobedad kordused ja need muutujanimed - $child, $child2, $child3 - need pole kah kellegi asi. Ja kui me siis peale selle koodi kirjutamist otsustame, et tahame tühikute asemel väljastada hoopis tärne, siis peame seda muutma igal menüütaseme puhul eraldi! Siin peab olema mingi parem moodus.

Ja tõesti. Siin tulebki meile appi rekursioon. Selle asemel et foreach'i sisse lõputult foreach'e toppida, pöördume hoopis sellesama print_menu() funktsiooni poole:

function print_menu($parent_id) {
    foreach (get_children($parent_id) as $child) {
        echo $child["nimi"]."\n";
        print_menu($child["id"]);
    }
}

Mnjaa.. see toimib, aga nüüd ei saa me enam print_menu() funktsiooni välja kutsuda ilma, et me talle argumendi '0' ette annaksime. Õnneks saab selle probleemi lahendada, kui määrame $parent_id väärtuseks vaikimisi 0:

function print_menu($parent_id=0) {

Nii... aga vahepeal läks täielikult kaduma ka meie tore treppimine. Kuid ka see mure on lihtsalt lahendatav. Me ju tahame välja printida täpselt nii palju tühikuid, kui mitmendal tasandil me parajasti oleme, seega anname lihtsalt kaasa veel ühe parameetri, mida ma igal alamtasandile suundumisel suurendame:

function print_menu($parent_id=0, $level=0) {
    foreach (get_children($parent_id) as $child) {
        // arvutame välja taande (0 tasandil on taane "")
        $taane = str_repeat(" ", $level);
        
        echo $taane . $child["nimi"]."\n";
        print_menu($child["id"], $level+1);
    }
}

Taraa... ja ongi valmis. Ja ei mingeid foreache foreachide sees. Kõik tänu rekursioonile.