Lehekülje Rekursioon lähteteksti vaatamine

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|Kanooniline näide: faktoriaali arvutamine]] - sobib lugemiseks neile, kes on vähe matemaatikalembesed,
* [[#Praktiline näide: Puukujulise menüü kuvamine andmebaasist|Praktiline näide: Puukujulise menüü kuvamine andmebaasist]]

== Kanooniline näide: faktoriaali arvutamine ==

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

: <var>n</var>! = 1 &middot; 2 &middot; 3 &middot; ... &middot; <var>n</var>

Näiteks arvu 3 faktoriaal on:

: 3! = 1 &middot; 2 &middot; 3 = 6

Ja arvu 4 faktoriaal on:

: 4! = 1 &middot; 2 &middot; 3 &middot; 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! &middot; 5 = 120

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

: <var>n</var>! = 1, kui <var>n</var> = 1
: <var>n</var>! = (<var>n</var> - 1)! &middot; <var>n</var>, kui <var>n</var> > 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:

{| border="1"
! 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:

{| border="1"
! 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:

{| border="1"
! 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'':

<pre>
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[];
}
</pre>

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:

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

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

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

Noh, ja nüüd ka kolmas tasand:

<pre>
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";
            }
        }
    }
}
</pre>

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:

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

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:

<pre>
function print_menu($parent_id=0) {
</pre>

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:

<pre>
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);
    }
}
</pre>

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