Was für Laien eine rekursive Funktion mit PHP ist

Kann mir bitte jemand eine rekursive Funktion in PHP (ohne Fibonacci) in Laiensprache und anhand von Beispielen erklären? Ich habe mir ein Beispiel angesehen, aber der Fibonacci hat mich total verloren!

Vielen Dank im Voraus 😉 Und wie oft verwenden Sie sie in der Webentwicklung?

Laienbegriffe:

Eine rekursive Funktion ist eine Funktion, die aufruft selbst

Etwas mehr in die Tiefe:

Wenn die Funktion sich ständig selbst aufruft, woher weiß sie, wann sie aufhören soll? Sie richten eine Bedingung ein, die als Basisfall bezeichnet wird. Basisfälle teilen unserem rekursiven Aufruf mit, wann er aufhören soll, andernfalls wird er endlos wiederholt.

Was für mich ein gutes Lernbeispiel war, da ich einen starken mathematischen Hintergrund habe Fakultät. Durch die Kommentare unten scheint die Fakultätsfunktion etwas zu viel zu sein, ich lasse es hier, nur für den Fall, dass Sie es wollten.

function fact($n) {
  if ($n === 0) { // our base case
     return 1;
  }
  else {
     return $n * fact($n-1); // <--calling itself.
  }
}

In Bezug auf die Verwendung rekursiver Funktionen in der Webentwicklung greife ich persönlich nicht auf rekursive Aufrufe zurück. Nicht, dass ich es für schlecht halten würde, sich auf Rekursion zu verlassen, aber sie sollten nicht Ihre erste Option sein. Sie können tödlich sein, wenn sie nicht richtig eingesetzt werden.

Obwohl ich mit dem Verzeichnisbeispiel nicht mithalten kann, hoffe ich, dass dies etwas hilft.

(20.04.10) Aktualisierung:

Es wäre auch hilfreich, diese Frage zu überprüfen, wo die akzeptierte Antwort in Laiensprache demonstriert, wie eine rekursive Funktion funktioniert. Obwohl sich die Frage des OP mit Java befasste, ist das Konzept dasselbe.

• Grundlegende Rekursion verstehen

Ein Beispiel wäre, jede Datei in einem beliebigen Unterverzeichnis eines bestimmten Verzeichnisses zu drucken (wenn Sie keine Symlinks in diesen Verzeichnissen haben, die die Funktion irgendwie unterbrechen könnten). Ein Pseudo-Code zum Drucken aller Dateien sieht folgendermaßen aus:

function printAllFiles($dir) {
    foreach (getAllDirectories($dir) as $f) {
        printAllFiles($f); // here is the recursive call
    }
    foreach (getAllFiles($dir) as $f) {
        echo $f;
    }
}

Die Idee ist, zuerst alle Unterverzeichnisse auszudrucken und dann die Dateien des aktuellen Verzeichnisses. Diese Idee wird auf alle Unterverzeichnisse angewendet, und das ist der Grund für den rekursiven Aufruf dieser Funktion für alle Unterverzeichnisse.

Wenn Sie dieses Beispiel ausprobieren möchten, müssen Sie nach den speziellen Verzeichnissen suchen . und ..sonst bleiben Sie beim Anrufen hängen printAllFiles(".") die ganze Zeit. Zusätzlich müssen Sie prüfen, was gedruckt werden soll und welches Ihr aktuelles Arbeitsverzeichnis ist (siehe opendir(), getcwd()…).

Rekursion ist etwas, das sich wiederholt. Wie eine Funktion, die sich selbst aus sich heraus aufruft. Lassen Sie es mich an einem etwas Pseudobeispiel demonstrieren:

Stell dir vor, du bist mit deinen Kumpels unterwegs und trinkst Bier, aber deine Frau wird dir die Hölle heiß machen, wenn du nicht vor Mitternacht nach Hause kommst. Lassen Sie uns zu diesem Zweck die Funktion orderAndDrinkBeer($time) erstellen, wobei $time gleich Mitternacht minus der Zeit ist, die Sie benötigen, um Ihr aktuelles Getränk auszutrinken und nach Hause zu kommen.

An der Bar angekommen, bestellen Sie also Ihr erstes Bier und beginnen mit dem Trinken:

$timeToGoHome="23";  // Let's give ourselves an hour for last call and getting home

function orderAndDrinkBeer($timeToGoHome) {  // Let's create the function that's going to call itself.
    $beer = New Beer();  // Let's grab ourselves a new beer
    $currentTime = date('G'); // Current hour in 24-hour format

    while ($beer->status != 'empty') {  // Time to commence the drinking loop
        $beer->drink();  // Take a sip or two of the beer(or chug if that's your preference)
    }

    // Now we're out of the drinking loop and ready for a new beer

    if ($currentTime < $timeToGoHome) { // BUT only if we got the time
        orderAndDrinkBeer($timeToGoHome);  // So we make the function call itself again!
    } else {  // Aw, snap!  It is time :S
        break; // Let's go home :(
    }
}

Hoffen wir nur, dass du nicht genug Bier getrunken hast, um so betrunken zu werden, dass deine Frau dich auf der Couch schlafen lässt, obwohl du pünktlich zu Hause bist -.-

Aber ja, das ist ziemlich genau, wie Rekursion geht.

Es ist eine Funktion, die sich selbst aufruft. Es ist nützlich, um bestimmte Datenstrukturen zu durchlaufen, die sich wiederholen, z. B. Bäume. Ein HTML-DOM ist ein klassisches Beispiel.

Ein Beispiel für eine Baumstruktur in Javascript und eine rekursive Funktion zum “Durchlaufen” des Baums.

    1
   / \
  2   3
     / \
    4   5

—

var tree = {
  id: 1,
  left: {
    id: 2,
    left: null,
    right: null
  },
  right: {
    id: 3,
    left: {
      id: 4,
      left: null,
      right: null
    },
    right: {
      id: 5,
      left: null,
      right: null
    }
  }
};

Um den Baum zu durchlaufen, rufen wir dieselbe Funktion wiederholt auf und übergeben die untergeordneten Knoten des aktuellen Knotens an dieselbe Funktion. Dann rufen wir die Funktion erneut auf, zuerst auf dem linken Knoten und dann auf dem rechten.

In diesem Beispiel erhalten wir die maximale Tiefe des Baums

var depth = 0;

function walkTree(node, i) {

  //Increment our depth counter and check
  i++;
  if (i > depth) depth = i;

  //call this function again for each of the branch nodes (recursion!)
  if (node.left != null) walkTree(node.left, i);
  if (node.right != null) walkTree(node.right, i);

  //Decrement our depth counter before going back up the call stack
  i--;
}

Schließlich rufen wir die Funktion auf

alert('Tree depth:' + walkTree(tree, 0));

Eine gute Möglichkeit, die Rekursion zu verstehen, besteht darin, den Code zur Laufzeit schrittweise durchzugehen.

Einfach ausgedrückt: Eine rekursive Funktion ist eine Funktion, die sich selbst aufruft.

Es ist sehr einfach, wenn eine Funktion sich selbst aufruft, um eine Aufgabe für unbestimmte und endliche Zeit zu erledigen. Ein Beispiel aus meinem eigenen Code, Funktion zum Auffüllen eines Kategoriebaums mit mehreren Ebenen

function category_tree($parent=0,$sep='')
{
    $q="select id,name from categorye where parent_id=".$parent;
    $rs=mysql_query($q);
    while($rd=mysql_fetch_object($rs))
    {
        echo('id.'">'.$sep.$rd->name.'');
        category_tree($rd->id,$sep.'--');
    }
}

Rekursion ist eine schicke Art zu sagen: “Mach das Ding noch einmal, bis es fertig ist”.

Zwei wichtige Dinge zu haben:

1. Ein Basisfall – Sie haben ein Ziel zu erreichen.
2. Ein Test – Wie Sie wissen, ob Sie dort angekommen sind, wo Sie hinwollen.

Stellen Sie sich eine einfache Aufgabe vor: Sortieren Sie einen Stapel Bücher alphabetisch. Ein einfacher Prozess wäre, die ersten beiden Bücher zu nehmen und sie zu sortieren. Jetzt kommt der rekursive Teil: Gibt es mehr Bücher? Wenn ja, wiederholen Sie es. Das “do it again” ist die Rekursion. Das “Gibt es noch Bücher” ist der Test. Und “nein, keine Bücher mehr” ist der Basisfall.