Rekursion

[CDS]

Hi an alle.

Bezüglich Rekursion:

Diese absolut simple rekursive Funktion macht mir jedoch Kopfzerbrechen, was die Verständlichkeit angeht:

  
<?php  
  function fak($n)  
    {  
        //Aufruf  
        echo "Eintritt mit $n<br>";  
            if ($n == 0)  
            {  
                return 1;  
            }  
            else  
            {  
                //echo "<br><br>";  
                $ergebnis = $n*fak($n-1);  
                //Rückspring  
                echo "Austritt mit $n: $ergebnis<br>";  
                return $ergebnis;  
            }  
    }  
  
    fak(5)  
?>

Das Ergebnis dieser Funktion ist folgendes:

  
Eintritt mit 5  
Eintritt mit 4  
Eintritt mit 3  
Eintritt mit 2  
Eintritt mit 1  
Eintritt mit 0  
Austritt mit 1: 1  
Austritt mit 2: 2  
Austritt mit 3: 6  
Austritt mit 4: 24  
Austritt mit 5: 120

Das mit dem "Einttritt" ist mir ja schon klar, da wird von 5 => 0 heruntergezählt, was durch den Teil

  
$ergebnis = $n*fak($n-1);  

geschieht.
Kann mir aber jemand bitte erklären, WO GENAU diese Funktion anfängt hoch zu zählen??
Was veranlasst diese Funktion nach "Eintritt mit 0", mit "Austritt mit 1" bis "Austritt mit 5" HOCH zu zählen?

Währe für jede hilfreiche Erklärung sehr dankbar :)

[Bademeister]

Hi,

Kann mir aber jemand bitte erklären, WO GENAU diese Funktion anfängt hoch zu zählen??

"Die Funktion" zählt nicht, weder hoch noch runter. Die Funktion wird fünf mal ausgeführt, und jede dieser Ausführungen macht unabhängig von den anderen ihre Ausgaben.

  

>                 $ergebnis = $n*fak($n-1);  
>                 //Rückspring  
>                 echo "Austritt mit $n: $ergebnis<br>";  
>                 return $ergebnis;  

Hier steht, dass fak(5) zuerst fak(4) ausführt, und *danach* "Austritt mit 5: 120" ausgibt. Bevor also diese Ausgabe von fak(5) getätigt wird, wird die *gesamte* Funktion fak(4) ausgeführt, die ihrerseits ihre Ausgabe tätigt, gleich nachdem sie die gesamte Funktion fak(3) ausgeführt hat, die ihrerseits........ oje, mir wird ganz schwindelig :-)

Viele Grüße,
der Bademeister

[bleicher]

Grüße,

rekursion funktioniert sowas wie -

1      2         3       4
             -->    --->     --->     --->
"Ebene": EINS    ZWEI    DREI    VIER        FÜNF
            <--      <--    <---     <----
             8        7       6        5
MFG
bleicher

[Beat]

Austritt mit 1: 1
Austritt mit 2: 2
Austritt mit 3: 6
Austritt mit 4: 24
Austritt mit 5: 120[/code]

Kann mir aber jemand bitte erklären, WO GENAU diese Funktion anfängt hoch zu zählen??

nicht hochzählen, das was reduziert, ist auch für den um 1 höheren Austritt des späteren prints der früheren=äusseren Schleife verantwortlich

mfg Beat

[dedlfix]

Hi!

Noch was ganz anderes:

if ($n == 0)
            {
                return 1;
            }
            else
            {
                ...
            }

Wenn im if-Zweig mit einem return (oder continue und break in Schleifen) garantiert der aktuelle Scope (hier die Funktion) verlassen wird, so benötigt man keine else-Kapslung mehr. Im Falle einer zutreffenden if-Bedingung wird die Funktion komplett verlassen. Der Anderenfalls-Code wird also in dem Fall nie erreicht und muss deshalb nicht mit einem else-Block vor der Ausführung "geschützt" werden.

Lo!

[CDS]

Ok, danke an alle, hab's verstanden ;-)