:: Anbieterverzeichnis ::

Globale Branchen

Informieren Sie sich über ausgewählte Unternehmen im Anbieterverzeichnis von SELFPHP

:: SELFPHP Forum ::

Fragen rund um die Themen PHP?
In über 130.000 Beiträgen finden Sie sicher die passende Antwort!

:: Newsletter ::

Abonnieren Sie hier den kostenlosen SELFPHP Newsletter!

Rekursive Funktionen: Seite 2

Seite drucken

SELFPHP ist Shopware Solution Partner

Shopware ist ein vielfach ausgezeichnetes Onlineshop-System der shopware AG, das auf PHP. Zend Framework und SQL basiert.

SELFPHP unterstützt Sie als Shopware Solution Partner bei der Konzeption, Programmierung und Realisierung Ihres Onlineshops und passt Shopware bei Bedarf an Ihre Unternehmensbedürfnisse an.

Weitere Informationen

Die mathematische Analyse ist hier ziemlich leicht, denn man sieht sofort, dass

f(n) = n * f(n-1)

ist. Damit hat man das Rekursionsprinzip bereits gefunden. Die Rekursion darf jedoch nicht ewig andauern, sie muss durch ein Abbruchkriterium angehalten werden. Dies ist die Bedingung 0!=1.

Lösung 2 (rekursiv)

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

echo fak(1) . " ";
echo fak(2) . " ";
echo fak(3) . " ";
echo fak(4) . " ";
?>

Ausgabe

1
2
6
24

Der else-Zweig wird angesprungen, wenn die Abbruchbedingung nicht erreicht wird. Hier ruft die Methode sich selbst wieder auf. Hierbei ist zu beachten, dass die Anweisung, die die Methode aufruft, noch gar nicht abgearbeitet werden kann, solange die aufgerufene Methode kein Ergebnis zurückliefert.

Der if-Zweig wird angesprungen, wenn die Abbruchbedingung erreicht ist.

Um Ihnen die Analyse zu vereinfachen, habe ich die rekursive Lösung etwas angepasst.

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

fak(4);
?>

Ausgabe

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

Zu jedem Aufruf gehört auch genau ein Rücksprung! Sie können dies beim Programmablauf mithilfe der eingefügten Ausgabezeilen nachvollziehen.

Man beachte die Anzahl der Aufrufe. Im iterativen Fall wird die Methode ein einziges Mal aufgerufen und im Schleifenkörper n Mal durchlaufen. Bei der rekursiven Berechnung wird die Methode n+1 Mal aufgerufen. Dabei muss jedes Mal Speicherplatz auf dem Stack reserviert werden. Da Parameter als lokale Variablen kopiert werden, wird auch dabei Speicherplatz verbraucht. Bei Rekursionen ist daher unbedingt darauf zu achten, dass die Abbruchbedingung bzw. das Rekursionsende korrekt implementiert wurde.

Rekursive Funktionen Seite 1

Rekursive Funktionen Seite 3