Objasnjenje rekurzivne funkcije

[ NenadS @ 22.08.2009. 20:47 ] @

Code:
    function fak($n)
    {
        echo "Ulaz $n<br>";

        if ($n == 0)
        {
            return 1;
        }
        else
        {
            $rezultat = $n*fak($n-1);
            echo "Izlaz $n = $rezultat<br>";
            return $rezultat;
        }
    }

Code:
Ulaz 5
Ulaz 4
Ulaz 3
Ulaz 2
Ulaz 1
Ulaz 0
Izlaz 1 = 1
Izlaz 2 = 2
Izlaz 3 = 6
Izlaz 4 = 24
Izlaz 5 = 120

Moze li neko da mi objasni princip rada ove funkcije. Zasto krajnje rezultate sortira od 1 do 5 i ispisuje ih na kraju, a ne izmedju svakog ulaza?

Hvala

[ Tudfa @ 22.08.2009. 21:11 ] @

Ako hoces takav izlaz uradi ovako:

Code:

<?php
function fak($num)
{
    if ($num == 0) return 1;
    return $num * fak($num - 1);
}

for($i = 1; $i <= 5; $i++)
{
    echo "ulaz = $i , izlaz = ".fak($i)."<br>";
}

?>

Dobices ovakav izlaz:

Code:

ulaz = 1 , izlaz = 1
ulaz = 2 , izlaz = 2
ulaz = 3 , izlaz = 6
ulaz = 4 , izlaz = 24
ulaz = 5 , izlaz = 120

Sto se tice rada te tvoje funkcije , sve u redu, ona racuna faktorijel nekog broja...

[ NenadS @ 22.08.2009. 21:29 ] @

Ne, nisi me dobro razumeo, ne treba mi drugaciji izlaz, vec mi treba objasnjenje zasto ovo ovako radi, to je sve :)

[ Nikola Poša @ 22.08.2009. 21:49 ] @

Samo prati kod...

Sve započinje ovim pozivom: fak(5). I onda odma' ide ispis Ulaz 5. Da li je 5 = 0? Nije, ide se na ovaj else, a u njemu je rekurzivan poziv, i to: 5*fak(4). Obrati pažnju da se posle te linije NE ide na ovu ispod, već se opet poziva f-ja fak(). To je i razlog zašto se prvo ispisuje tih pet redova "Ulaz x"...

Kad se stigne do momenta kada je poziv 1*fak(0), to će dati rezultat 1, bez rekurzivnog poziva, pošto će se ući u taj prvi if (if ($num == 0)), i onda kreće taj ispis "Izlaz...". I onda sve ide "u nazad" pošto je životni vek te promenljiva $rezultat samo unutar f-je fak(), a imao si rekurzivne pozive koji su toj promenljivoj dodeljivali vrednosti.

Bilo bi najbolje kad bi nekako mogao da ti nacrtam sve to...

_{[Ovu poruku je menjao Nikola Poša dana 22.08.2009. u 22:59 GMT+1]}

[ NenadS @ 22.08.2009. 22:16 ] @

Ovaj prvi deo razumem zasto prvo ispisuje od 5 do 0 ali ne razumem drugi deo gde ispisuje od 1 do 5 kada tu ne vidim nikakvu petlju ili rekurzivno pozivanje? To mi nije jasno :(

[ Goran Rakić @ 22.08.2009. 23:07 ] @

Zato što svaki poziv funkcije fak() završava ispisom rezultata. Evo slične ilustracije:

Vidiš kako kada fak(2) pozove fak(1) i ona pozove fak(0) prvo rezultat ispisuje fak(0), pa onda se nastavi izvršavanje fak(1), i tako do poslednje funkcije.

Citat:

Tudfa: Ako hoces takav izlaz uradi ovako...

Nadam se da ti je jasna implikacija na brzinu tvog koda jer za svaku iteraciju računaš celo rekurzivno spuštanje. Bolje je:

Code:

<?php
function fak($num) {
    if ($num == 0) return 1;
    $res = $num * fak($num - 1);
    echo "ulaz = $num, izlaz = $res<br>\n";
    return $res;
}

fak(5);
?>

_{[Ovu poruku je menjao Goran Rakić dana 23.08.2009. u 00:19 GMT+1]}

[ Tudfa @ 22.08.2009. 23:57 ] @

Citat:

Goran Rakić: Nadam se da ti je jasna implikacija na brzinu tvog koda jer za svaku iteraciju računaš celo rekurzivno spuštanje.

Da u pravu si, bilo bi vise poziva funkcije sto je veci broj za koji se trazi faktorijel, hvala na hintu Gorane