:: 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 1

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

Sie werden nun noch eine weitere Methode kennenlernen, Funktionen zu verwenden. Es handelt sich dabei um rekursive Funktionen. Dies ist eine Funktion, die sich selbst aufruft. Rekursive Funktionen werden vor allem dort eingesetzt, wo man nicht genau vorherbestimmen kann, wie verschachtelt eine Datenstruktur ist.

Rekursion allgemein

Unter einer Rekursion versteht man die Definition eines Programms, einer Funktion oder eines Verfahrens durch sich selbst. Rekursive Darstellungen sind im Allgemeinen kürzer und leichter verständlich als andere Darstellungen, da sie die charakteristischen Eigenschaften einer Funktion betonen.

Ein Algorithmus heißt rekursiv, wenn er Abschnitte enthält, die sich selbst aufrufen. Er heißt iterativ, wenn bestimmte Abschnitte des Algorithmus innerhalb einer einzigen Ausführung des Algorithmus mehrfach durchlaufen werden. Iteration und Rekursion können oft alternativ in Programmen eingesetzt werden, da man jede Iteration in eine Rekursion umformen kann, und umgekehrt. In der Praxis liegt jedoch oftmals die iterative oder die rekursive Lösung auf der Hand und die jeweils alternative Form ist gar nicht so leicht zu bestimmen.

Hinweis: Programmtechnisch läuft eine Iteration auf eine Schleife, eine Rekursion auf den Aufruf einer Methode durch sich selbst hinaus.

Fallbeispiel

Nehmen Sie einen Papierstreifen und versuchen Sie ihn so zu falten, dass sieben genau gleich große Teile entstehen. Dabei dürfen Sie kein Lineal oder sonst ein Hilfsmittel verwenden. Sie werden feststellen, das die Aufgabe gar nicht so einfach ist!

Wenn Sie statt sieben jedoch acht Teile machen, wird es plötzlich einfach: Einmal in der Mitte falten, dann nochmals falten ...

Genau das ist das Prinzip der Rekursion: Ein Problem wird auf ein »kleineres« Problem zurückgeführt, das wiederum nach demselben Verfahren bearbeitet wird. Rekursion ist eine wichtige algorithmische Technik.

Am obigen Beispiel haben Sie auch gesehen, dass die Lösung einer Aufgabe, wenn sie mit Rekursion möglich ist, sehr einfach gelöst werden kann. Hier nun zwei rekursive Fallbeispiele.

Fakultät einer Zahl n (n!) rekursiv

Bei der Berechnung der Fakultätsfunktion geht man aus von der Definition der Fakultät:
0! = 1
n! = 1 * 2 * 3 * ... * n für n>0

Man beginnt bei den kleinen Zahlen. Der Wert von O! ist 1, der Wert von 1! ist 0!*1, der Wert von 2! ist 1!*2, der Wert von 3! ist 2!*3 usw.

Nimmt man eine Schleifenvariable $i, die von 1 bis n durchgezählt wird, so muss innerhalb der Schleife lediglich der Wert der Fakultät vom vorhergehenden Schleifendurchlauf mit dem Wert der Schleifenvariablen multipliziert werden.

Lösung 1 (iterativ)

<?php
function fak($n) {
  $resultat = 1;
  for ($i=1; $i<=$n; $i++) {
    $resultat = $i*$resultat;
  }
  return $resultat;
}
echo fak(1) . "<br>";
echo fak(2) . "<br>";
echo fak(3) . "<br>";
echo fak(4) . "<br>";
?>

Ausgabe

1
2
6
24

Bei der rekursiven Berechnung der Fakultätsfunktion geht man ebenfalls von der Definition der Fakultät aus, beginnt jedoch nicht bei den kleinen Zahlen, sondern bei den großen Zahlen und läuft dann zu den kleinen Zahlen zurück (recurrere = lat. zurücklaufen).
n! = 1 * 2 * 3 * ... * n für n>0
0! = 1

Im Gegensatz zur Iteration schaut man jetzt auf die Funktion f(n) und versucht, diese Funktion durch sich selbst, aber mit anderen Aufrufparametern darzustellen.

Variablenfunktionen

Rekursive Funktionen Seite 2