Was für Laien eine rekursive Funktion ist, die PHP verwendet

Question 1

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 die Fibonacci haben mich total verloren!

Vielen Dank im Voraus ;-) Auch wie oft verwenden Sie sie in der Webentwicklung?

Question 2

Laienbegriffe:

Eine rekursive Funktion ist eine Funktion, die sich selbst aufruft

Etwas ausführlicher:

Wenn sich die Funktion weiterhin selbst aufruft, woher weiß sie dann, wann sie beendet werden muss? Sie richten eine Bedingung ein, die als Basisfall bezeichnet wird. Basisfälle teilen unserem rekursiven Aufruf mit, wann er zu stoppen ist, andernfalls wird eine Endlosschleife ausgeführt.

Was für mich ein gutes Lernbeispiel war, da ich einen starken Hintergrund in Mathematik habe, war faktoriell . Nach den Kommentaren unten scheint die Fakultätsfunktion etwas zu viel zu sein. Ich lasse sie 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 eine schlechte Praxis 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 verwendet werden.

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

(20.04.10) Update:

Es wäre auch hilfreich, diese Frage zu lesen, in der die akzeptierte Antwort Laien zeigt, wie eine rekursive Funktion funktioniert. Obwohl sich die Frage des OP mit Java befasste, ist das Konzept dasselbe:

Grundlegende Rekursion verstehen

Question 3

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 möglicherweise irgendwie beeinträchtigen). Ein Pseudocode 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 und dann die Dateien des aktuellen Verzeichnisses zu drucken. Diese Idee wird auf alle Unterverzeichnisse angewendet. Dies ist der Grund für den rekursiven Aufruf dieser Funktion für alle Unterverzeichnisse.

Wenn Sie dieses Beispiel ausprobieren möchten Sie für die speziellen Verzeichnisse zu überprüfen .und .., sonst bekommen Sie stecken in ruft die printAllFiles(".")ganze Zeit. Zusätzlich müssen Sie überprüfen , was zu drucken und was Ihr aktuelles Arbeitsverzeichnis ist (siehe opendir(), getcwd(), ...).

Question 4

Rekursion ist etwas, das sich wiederholt. Wie eine Funktion, die sich aus sich heraus aufruft. Lassen Sie mich in einem etwas pseudo-Beispiel demonstrieren:

Stellen Sie sich vor, Sie sind mit Ihren Freunden unterwegs, um Bier zu trinken, aber Ihre Frau wird Ihnen die Hölle geben, wenn Sie nicht vor Mitternacht nach Hause kommen. Zu diesem Zweck erstellen wir die Funktion orderAndDrinkBeer ($ time), bei der $ time Mitternacht ist, abzüglich der Zeit, die Sie benötigen, um Ihr aktuelles Getränk zu beenden und nach Hause zu kommen.

Wenn Sie an der Bar ankommen, bestellen Sie 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 jetzt nur, dass Sie nicht genug Bier trinken konnten, um so betrunken zu werden, dass Ihre Frau Sie auf der Couch schlafen lässt, unabhängig davon, ob Sie pünktlich zu Hause sind.

Aber ja, so läuft Rekursion ab.

Question 5

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 "Gehen" des Baums.

- -

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. Wir rufen dann die Funktion erneut auf, zuerst am linken Knoten und dann am 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 zu durchlaufen.

Question 6

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

Question 7

Es ist sehr einfach, wenn sich eine Funktion selbst aufruft, um eine Aufgabe für eine undefinierte und endliche Zeitspanne auszuführen. Ein Beispiel aus meinem eigenen Code, Funktion zum Auffüllen eines mit mehrstufigen Kategoriebaums

Funktion category_tree ($ parent = 0, $ sep = '')
{
    $ q = "ID auswählen, Name aus Kategorie, wobei parent_id =". $ parent;
    $ rs = mysql_query ($ q);
    while ($ rd = mysql_fetch_object ($ rs))
    {
        echo ('id.' "> '. $ sep. $ rd-> name.' ');
        category_tree ($ rd-> id, $ sep .'-- ');
    }}
}}

Question 8

Rekursion ist eine ausgefallene Art zu sagen: "Mach das Ding noch einmal, bis es fertig ist."

Zwei wichtige Dinge zu haben:

Ein Basisfall - Sie haben ein Ziel zu erreichen.
Ein Test - Wie Sie wissen, ob Sie dahin müssen, wohin Sie gehen.

Stellen Sie sich eine einfache Aufgabe vor: Sortieren Sie einen Stapel Bücher alphabetisch. Ein einfacher Vorgang wäre, die ersten beiden Bücher zu sortieren. Nun kommt hier der rekursive Teil: Gibt es mehr Bücher? Wenn ja, machen Sie es noch einmal. Das "mach es nochmal" ist die Rekursion. Das "Gibt es noch mehr Bücher" ist der Test. Und "nein, keine Bücher mehr" ist der Basisfall.

Question 9

Die beste Erklärung, die ich gefunden habe, als ich erfuhr, dass ich hier bin: http://www.elated.com/articles/php-recursive-functions/

Es ist, weil eine Sache:

Die aufgerufene Funktion wird im Speicher erstellt (neue Instanz wird erstellt)

Die rekursive Funktion ruft sich also nicht selbst auf , sondern ruft eine andere Instanz auf - es ist also nicht eine Funktion im Speicher, die etwas Magie ausübt . Es gibt einige Instanzen im Speicher, die sich selbst einige Werte zurückgeben - und dieses Verhalten ist dasselbe, wenn beispielsweise Funktion a Funktion b aufruft. Sie haben zwei Instanzen sowie eine rekursive Funktion, die als neue Instanz von sich selbst bezeichnet wird.

Versuchen Sie, Speicher mit Instanzen auf Papier zu zeichnen - es wird Sinn machen.

Question 10

Rekursion ist eine Alternative zu Schleifen. Es ist ziemlich selten, dass sie Ihrem Code mehr Klarheit oder Eleganz verleihen. Ein gutes Beispiel war die Antwort von Progman. Wenn er keine Rekursion verwenden würde, wäre er gezwungen zu verfolgen, in welchem Verzeichnis er sich gerade befindet (dies wird als Status bezeichnet). Rekursionen ermöglichen es ihm, die Buchhaltung mithilfe des Stapels (dem Bereich, in dem Variablen vorhanden sind) durchzuführen und Rücksprungadresse einer Methode werden gespeichert)

Die Standardbeispiele Fakultät und Fibonacci sind für das Verständnis des Konzepts nicht hilfreich, da sie leicht durch eine Schleife ersetzt werden können.

Question 11

Grundsätzlich das. Es ruft sich so lange an, bis es fertig ist

void print_folder(string root)
{
    Console.WriteLine(root);
    foreach(var folder in Directory.GetDirectories(root))
    {
        print_folder(folder);
    }
}

Funktioniert auch mit Loops!

void pretend_loop(int c)
{
    if(c==0) return;
    print "hi";
    pretend_loop(c-);
}

Sie können auch versuchen, es zu googeln. Beachten Sie das "Meinten Sie" (klicken Sie darauf ...). http://www.google.com/search?q=recursion&spell=1

Question 12

Hier ist ein praktisches Beispiel (es gibt bereits mehrere gute). Ich wollte nur eine hinzufügen, die für fast jeden Entwickler nützlich ist.

Irgendwann müssen Entwickler ein Objekt wie bei einer Antwort von einer API oder einem Objekt- oder Array-Typ analysieren.

Diese Funktion wird zunächst aufgerufen, um ein Objekt zu analysieren, das möglicherweise nur Parameter enthält. Was ist jedoch, wenn das Objekt auch andere Objekte oder Arrays enthält? Dies muss behoben werden, und zum größten Teil tut dies die Grundfunktion bereits, sodass die Funktion sich selbst erneut aufruft (nachdem bestätigt wurde, dass der Schlüssel oder Wert entweder ein Objekt oder ein Array ist) und dieses neue Objekt oder Array analysiert. Letztendlich wird eine Zeichenfolge zurückgegeben, die jeden Parameter in einer Zeile zur besseren Lesbarkeit für sich erstellt. Sie können die Werte jedoch genauso einfach in einer Protokolldatei protokollieren oder in eine Datenbank oder was auch immer einfügen.

Ich habe den $prefixParameter hinzugefügt , um das übergeordnete Element zur Beschreibung der Endvariablen zu verwenden, damit wir sehen können, worauf sich der Wert bezieht. Es enthält keine Dinge wie Nullwerte, aber dies kann aus diesem Beispiel geändert werden.

Wenn Sie das Objekt haben:

$apiReturn = new stdClass();
$apiReturn->shippingInfo = new stdClass();
$apiReturn->shippingInfo->fName = "Bill";
$apiReturn->shippingInfo->lName = "Test";
$apiReturn->shippingInfo->address1 = "22 S. Deleware St.";
$apiReturn->shippingInfo->city = "Chandler";
$apiReturn->shippingInfo->state = "AZ";
$apiReturn->shippingInfo->zip = 85225;
$apiReturn->phone = "602-312-4455";
$apiReturn->transactionDetails = array(
    "totalAmt" => "100.00",
     "currency" => "USD",
     "tax" => "5.00",
     "shipping" => "5.00"
);
$apiReturn->item = new stdClass();
$apiReturn->item->name = "T-shirt";
$apiReturn->item->color = "blue";
$apiReturn->item->itemQty = 1;

und verwenden:

var_dump($apiReturn);

es wird zurückkehren:

Objekt (stdClass) # 1 (4) {["Versandinformationen"] => Objekt (stdClass) # 2 (6) {["fName"] => Zeichenfolge (4) "Rechnung" ["lName"] => Zeichenfolge ( 4) "Test" ["Adresse1"] => Zeichenfolge (18) "22 S. Deleware St." ["city"] => string (8) "Chandler" ["state"] => string (2) "AZ" ["zip"] => int (85225)} ["phone"] => string (12 ) "602-312-4455" ["transactionDetails"] => Array (4) {["totalAmt"] => Zeichenfolge (6) "100.00" ["Währung"] => Zeichenfolge (3) "USD" [" Steuer "] => Zeichenfolge (4)" 5,00 "[" Versand "] => Zeichenfolge (4)" 5,00 "} [" Artikel "] => Objekt (stdClass) # 3 (3) {[" Name "] = > string (7) "T-Shirt" ["Farbe"] =>

und hier ist der Code, um ihn in einen String mit einem Zeilenumbruch für jeden Parameter zu analysieren:

function parseObj($obj, $prefix = ''){
    $stringRtrn = '';
    foreach($obj as $key=>$value){
        if($prefix){
            switch ($key) {
                case is_array($key):
                    foreach($key as $k=>$v){
                        $stringRtrn .= parseObj($key, $obj);
                    }
                    break;
                case is_object($key):
                    $stringRtrn .= parseObj($key, $obj);
                    break;
                default:
                    switch ($value) {
                        case is_array($value):
                            $stringRtrn .= parseObj($value, $key);
                            break;
                        case is_object($value):
                            $stringRtrn .= parseObj($value, $key);
                            break;
                        default:
                            $stringRtrn .= $prefix ."_". $key ." = ". $value ."<br>";
                            break;
                    }
                    break;
            }
        } else { // end if($prefix)
            switch($key){
                case is_array($key):
                    $stringRtrn .= parseObj($key, $obj);
                    break;
                case is_object($key):

                    $stringRtrn .= parseObj($key, $obj);
                    break;
                default:
                    switch ($value) {
                        case is_array($value):
                            $stringRtrn .= parseObj($value, $key);
                            break;
                        case is_object($value):
                            $stringRtrn .= parseObj($value, $key);
                            break;                      
                        default:
                            $stringRtrn .= $key ." = ". $value ."<br>";
                            break;
                    } // end inner switch 
            } // end outer switch
        } // end else
    } // end foreach($obj as $key=>$value)
    return $stringRtrn;
} // END parseObj()

Dadurch wird das Objekt wie folgt zurückgegeben:

shippingInfo_fName = Bill
shippingInfo_lName = Test
shippingInfo_address1 = 22 S. Deleware St.
shippingInfo_city = Chandler
shippingInfo_state = AZ
shippingInfo_zip = 85225
phone = 602-312-4455
transactionDetails_totalAmt = 100.00
transactionDetails_currency = USD
transactionDetails_tax = 5.00
transactionDetails_shipping = 5.00
item_name = T-shirt
item_color = blue
item_itemQty = 1

Ich habe die verschachtelten switch- Anweisungen ausgeführt, um Verwechslungen mit zu vermeiden if . . . ifelse . . . else, aber es war fast genauso lang. Wenn es hilft, fragen Sie einfach nach den if-Bedingungen und ich kann sie für diejenigen einfügen, die sie benötigen.

Question 13

Das Durchlaufen eines Verzeichnisbaums ist ein gutes Beispiel. Sie können etwas Ähnliches tun, um ein Array zu verarbeiten. Hier ist eine wirklich einfache rekursive Funktion, die einfach eine Zeichenfolge, ein einfaches Array von Zeichenfolgen oder ein verschachteltes Array von Zeichenfolgen beliebiger Tiefe verarbeitet und Instanzen von 'Hallo' durch 'Auf Wiedersehen' in der Zeichenfolge oder den Werten des Arrays oder einer beliebigen Zeichenfolge ersetzt Unterarray:

function replaceHello($a) {
    if (! is_array($a)) {
        $a = str_replace('hello', 'goodbye', $a);
    } else {
        foreach($a as $key => $value) {
            $a[$key] = replaceHello($value);
        }
    }
    return $a
}

Es weiß, wann es beendet werden muss, da das "Ding", das es verarbeitet, irgendwann kein Array mehr ist. Wenn Sie beispielsweise replaceHello ('Hallo') aufrufen, wird 'Auf Wiedersehen' zurückgegeben. Wenn Sie ihm ein Array von Zeichenfolgen senden, obwohl es sich für jedes Mitglied des Arrays einmal selbst aufruft, geben Sie das verarbeitete Array zurück.

Question 14

Wenn Sie Anthony Forloneys Beispiel einen bestimmten Wert hinzufügen (z. B. "1"), ist alles klar:

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

Original:

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

Question 15

Dies ist ein sehr einfaches Beispiel für Fakultät mit Rekursion:

Fakultäten sind ein sehr einfaches mathematisches Konzept. Sie sind wie 5 geschrieben! und das bedeutet 5 * 4 * 3 * 2 * 1. Also 6! ist 720 und 4! ist 24.

function factorial($number) { 

    if ($number < 2) { 
        return 1; 
    } else { 
        return ($number * factorial($number-1)); 
    } 
}

Ich hoffe, das ist nützlich für Sie. :) :)

Question 16

Es funktioniert ein einfaches Beispiel rekursiv (Y)

<?php 


function factorial($y,$x) { 

    if ($y < $x) { 
        echo $y; 
    } else { 
        echo $x; 
        factorial($y,$x+1);
    } 
}

$y=10;

$x=0;
factorial($y,$x);

 ?>

Question 17

Rekursion für Kaprekars Konstante

function KaprekarsConstant($num, $count = 1) {
    $input = str_split($num);
    sort($input);

    $ascendingInput  = implode($input);
    $descendingInput = implode(array_reverse($input));

    $result = $ascendingInput > $descendingInput 
        ? $ascendingInput - $descendingInput 
        : $descendingInput - $ascendingInput;

    if ($result != 6174) {
        return KaprekarsConstant(sprintf('%04d', $result), $count + 1);
    }

    return $count;

}}

Die Funktion ruft sich mit dem Ergebnis der Berechnung so lange auf, bis sie die Kaprekars-Konstante erreicht, und gibt die Häufigkeit zurück, mit der die Berechnungen durchgeführt wurden.

/ edit Für alle, die Kaprekars Constant nicht kennen, ist eine Eingabe von 4 Ziffern mit mindestens zwei unterschiedlichen Ziffern erforderlich.

Answer 1

72

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 die Fibonacci haben mich total verloren!

Vielen Dank im Voraus ;-) Auch wie oft verwenden Sie sie in der Webentwicklung?

php function recursion Imran
quelle

142

Lesen Sie stackoverflow.com/questions/2648968 durch und es wird irgendwann Sinn machen.

Kevin

23

Oder versuchen Sie den Link Did You Mean bei Google: google.com/search?hl=de&q=recursion

Gordon

9

@kevin vielleicht solltest du den Kommentar als "duplicate stackoverflow.com/questions/2648968 " schreiben ;)

Progman

20

@ Kevin: Aber du hast den Basisfall vergessen! Auf diese Weise lernt er keine Rekursion, sondern klickt einfach weiter darauf, bis sein Stapel überläuft. :(

CA McCann

3

@ Camccann angemessen, würde ich denken, angesichts der Website, auf der wir sind

Amber

Answer 2

142

Lesen Sie stackoverflow.com/questions/2648968 durch und es wird irgendwann Sinn machen.

Kevin

Answer 3

23

Oder versuchen Sie den Link Did You Mean bei Google: google.com/search?hl=de&q=recursion

Gordon

Answer 4

9

@kevin vielleicht solltest du den Kommentar als "duplicate stackoverflow.com/questions/2648968 " schreiben ;)

Progman

Answer 5

20

@ Kevin: Aber du hast den Basisfall vergessen! Auf diese Weise lernt er keine Rekursion, sondern klickt einfach weiter darauf, bis sein Stapel überläuft. :(

CA McCann

Answer 6

3

@ Camccann angemessen, würde ich denken, angesichts der Website, auf der wir sind

Amber

Answer 7

Laienbegriffe:

Eine rekursive Funktion ist eine Funktion, die sich selbst aufruft

Etwas ausführlicher:

Wenn sich die Funktion weiterhin selbst aufruft, woher weiß sie dann, wann sie beendet werden muss? Sie richten eine Bedingung ein, die als Basisfall bezeichnet wird. Basisfälle teilen unserem rekursiven Aufruf mit, wann er zu stoppen ist, andernfalls wird eine Endlosschleife ausgeführt.

Was für mich ein gutes Lernbeispiel war, da ich einen starken Hintergrund in Mathematik habe, war faktoriell . Nach den Kommentaren unten scheint die Fakultätsfunktion etwas zu viel zu sein. Ich lasse sie 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 eine schlechte Praxis 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 verwendet werden.

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

(20.04.10) Update:

Es wäre auch hilfreich, diese Frage zu lesen, in der die akzeptierte Antwort Laien zeigt, wie eine rekursive Funktion funktioniert. Obwohl sich die Frage des OP mit Java befasste, ist das Konzept dasselbe:

Grundlegende Rekursion verstehen

Answer 8

5

Obwohl Ihr Beispiel es gut erklärt, kann das Beispiel für Laien kaum als Beispiel angesehen werden. Wenn OP ein bisschen Probleme hat, die Rekursion anhand eines Fibonacci-Beispiels zu verstehen, kann ich mir vorstellen, dass Fakultäten sie auch nicht schneiden werden. Besonders bei diesen mathematischen Definitionen.

Anständiger Dabbler

Answer 9

@fireeyedboy, stereofrog: Im College wurde mir beim Lernen der Rekursion eine faktorielle Funktion beigebracht, die mich zum Klicken brachte. Das OP und ich haben wahrscheinlich unterschiedliche mathematische Hintergründe, aber ich habe die faktorielle Definition der Kürze halber weggelassen und meine Laiendefinition der Rekursion betont.

Anthony Forloney

Answer 10

Es ist nicht erforderlich, eine Endbedingung (Basisfall) für eine Funktion zu haben, die Ihre Definition leicht falsch macht. (Obwohl in PHP Sie sonst müssen Sie mit einem Stapelüberlauf enden)

Yacoby

Answer 11

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 möglicherweise irgendwie beeinträchtigen). Ein Pseudocode 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 und dann die Dateien des aktuellen Verzeichnisses zu drucken. Diese Idee wird auf alle Unterverzeichnisse angewendet. Dies ist der Grund für den rekursiven Aufruf dieser Funktion für alle Unterverzeichnisse.

Wenn Sie dieses Beispiel ausprobieren möchten Sie für die speziellen Verzeichnisse zu überprüfen .und .., sonst bekommen Sie stecken in ruft die printAllFiles(".")ganze Zeit. Zusätzlich müssen Sie überprüfen , was zu drucken und was Ihr aktuelles Arbeitsverzeichnis ist (siehe opendir(), getcwd(), ...).

Answer 12

2

Ich mag diese Antwort besser als die faktorielle, weil sie tatsächlich zutrifft. Wie viele Personen müssen tatsächlich jemals Fakultäten berechnen, und warum sollten Sie Fakultäten überhaupt rekursiv durchführen (Memoisierung vielleicht, aber zu diesem Zeitpunkt, warum nicht einfach von Anfang an eine Nachschlagetabelle verwenden).

Davidtbernal

Answer 13

Rekursion ist etwas, das sich wiederholt. Wie eine Funktion, die sich aus sich heraus aufruft. Lassen Sie mich in einem etwas pseudo-Beispiel demonstrieren:

Stellen Sie sich vor, Sie sind mit Ihren Freunden unterwegs, um Bier zu trinken, aber Ihre Frau wird Ihnen die Hölle geben, wenn Sie nicht vor Mitternacht nach Hause kommen. Zu diesem Zweck erstellen wir die Funktion orderAndDrinkBeer ($ time), bei der $ time Mitternacht ist, abzüglich der Zeit, die Sie benötigen, um Ihr aktuelles Getränk zu beenden und nach Hause zu kommen.

Wenn Sie an der Bar ankommen, bestellen Sie 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 jetzt nur, dass Sie nicht genug Bier trinken konnten, um so betrunken zu werden, dass Ihre Frau Sie auf der Couch schlafen lässt, unabhängig davon, ob Sie pünktlich zu Hause sind.

Aber ja, so läuft Rekursion ab.

Answer 14

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 "Gehen" des Baums.

- -

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. Wir rufen dann die Funktion erneut auf, zuerst am linken Knoten und dann am 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 zu durchlaufen.

Answer 15

8

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

Samuel
quelle

Answer 16

Es ist sehr einfach, wenn sich eine Funktion selbst aufruft, um eine Aufgabe für eine undefinierte und endliche Zeitspanne auszuführen. Ein Beispiel aus meinem eigenen Code, Funktion zum Auffüllen eines mit mehrstufigen Kategoriebaums

Funktion category_tree ($ parent = 0, $ sep = '')
{
    $ q = "ID auswählen, Name aus Kategorie, wobei parent_id =". $ parent;
    $ rs = mysql_query ($ q);
    while ($ rd = mysql_fetch_object ($ rs))
    {
        echo ('id.' "> '. $ sep. $ rd-> name.' ');
        category_tree ($ rd-> id, $ sep .'-- ');
    }}
}}

Answer 17

Rekursion ist eine ausgefallene Art zu sagen: "Mach das Ding noch einmal, bis es fertig ist."

Zwei wichtige Dinge zu haben:

Ein Basisfall - Sie haben ein Ziel zu erreichen.
Ein Test - Wie Sie wissen, ob Sie dahin müssen, wohin Sie gehen.

Stellen Sie sich eine einfache Aufgabe vor: Sortieren Sie einen Stapel Bücher alphabetisch. Ein einfacher Vorgang wäre, die ersten beiden Bücher zu sortieren. Nun kommt hier der rekursive Teil: Gibt es mehr Bücher? Wenn ja, machen Sie es noch einmal. Das "mach es nochmal" ist die Rekursion. Das "Gibt es noch mehr Bücher" ist der Test. Und "nein, keine Bücher mehr" ist der Basisfall.

Answer 18

Die beste Erklärung, die ich gefunden habe, als ich erfuhr, dass ich hier bin: http://www.elated.com/articles/php-recursive-functions/

Es ist, weil eine Sache:

Die aufgerufene Funktion wird im Speicher erstellt (neue Instanz wird erstellt)

Die rekursive Funktion ruft sich also nicht selbst auf , sondern ruft eine andere Instanz auf - es ist also nicht eine Funktion im Speicher, die etwas Magie ausübt . Es gibt einige Instanzen im Speicher, die sich selbst einige Werte zurückgeben - und dieses Verhalten ist dasselbe, wenn beispielsweise Funktion a Funktion b aufruft. Sie haben zwei Instanzen sowie eine rekursive Funktion, die als neue Instanz von sich selbst bezeichnet wird.

Versuchen Sie, Speicher mit Instanzen auf Papier zu zeichnen - es wird Sinn machen.

Answer 19

Rekursion ist eine Alternative zu Schleifen. Es ist ziemlich selten, dass sie Ihrem Code mehr Klarheit oder Eleganz verleihen. Ein gutes Beispiel war die Antwort von Progman. Wenn er keine Rekursion verwenden würde, wäre er gezwungen zu verfolgen, in welchem Verzeichnis er sich gerade befindet (dies wird als Status bezeichnet). Rekursionen ermöglichen es ihm, die Buchhaltung mithilfe des Stapels (dem Bereich, in dem Variablen vorhanden sind) durchzuführen und Rücksprungadresse einer Methode werden gespeichert)

Die Standardbeispiele Fakultät und Fibonacci sind für das Verständnis des Konzepts nicht hilfreich, da sie leicht durch eine Schleife ersetzt werden können.

Answer 20

Grundsätzlich das. Es ruft sich so lange an, bis es fertig ist

void print_folder(string root)
{
    Console.WriteLine(root);
    foreach(var folder in Directory.GetDirectories(root))
    {
        print_folder(folder);
    }
}

Funktioniert auch mit Loops!

void pretend_loop(int c)
{
    if(c==0) return;
    print "hi";
    pretend_loop(c-);
}

Sie können auch versuchen, es zu googeln. Beachten Sie das "Meinten Sie" (klicken Sie darauf ...). http://www.google.com/search?q=recursion&spell=1

Answer 21

Tippfehler ... (Wo ist Ihre

Endklammer

Answer 22

Hier ist ein praktisches Beispiel (es gibt bereits mehrere gute). Ich wollte nur eine hinzufügen, die für fast jeden Entwickler nützlich ist.

Irgendwann müssen Entwickler ein Objekt wie bei einer Antwort von einer API oder einem Objekt- oder Array-Typ analysieren.

Diese Funktion wird zunächst aufgerufen, um ein Objekt zu analysieren, das möglicherweise nur Parameter enthält. Was ist jedoch, wenn das Objekt auch andere Objekte oder Arrays enthält? Dies muss behoben werden, und zum größten Teil tut dies die Grundfunktion bereits, sodass die Funktion sich selbst erneut aufruft (nachdem bestätigt wurde, dass der Schlüssel oder Wert entweder ein Objekt oder ein Array ist) und dieses neue Objekt oder Array analysiert. Letztendlich wird eine Zeichenfolge zurückgegeben, die jeden Parameter in einer Zeile zur besseren Lesbarkeit für sich erstellt. Sie können die Werte jedoch genauso einfach in einer Protokolldatei protokollieren oder in eine Datenbank oder was auch immer einfügen.

Ich habe den $prefixParameter hinzugefügt , um das übergeordnete Element zur Beschreibung der Endvariablen zu verwenden, damit wir sehen können, worauf sich der Wert bezieht. Es enthält keine Dinge wie Nullwerte, aber dies kann aus diesem Beispiel geändert werden.

Wenn Sie das Objekt haben:

$apiReturn = new stdClass();
$apiReturn->shippingInfo = new stdClass();
$apiReturn->shippingInfo->fName = "Bill";
$apiReturn->shippingInfo->lName = "Test";
$apiReturn->shippingInfo->address1 = "22 S. Deleware St.";
$apiReturn->shippingInfo->city = "Chandler";
$apiReturn->shippingInfo->state = "AZ";
$apiReturn->shippingInfo->zip = 85225;
$apiReturn->phone = "602-312-4455";
$apiReturn->transactionDetails = array(
    "totalAmt" => "100.00",
     "currency" => "USD",
     "tax" => "5.00",
     "shipping" => "5.00"
);
$apiReturn->item = new stdClass();
$apiReturn->item->name = "T-shirt";
$apiReturn->item->color = "blue";
$apiReturn->item->itemQty = 1;

und verwenden:

var_dump($apiReturn);

es wird zurückkehren:

Objekt (stdClass) # 1 (4) {["Versandinformationen"] => Objekt (stdClass) # 2 (6) {["fName"] => Zeichenfolge (4) "Rechnung" ["lName"] => Zeichenfolge ( 4) "Test" ["Adresse1"] => Zeichenfolge (18) "22 S. Deleware St." ["city"] => string (8) "Chandler" ["state"] => string (2) "AZ" ["zip"] => int (85225)} ["phone"] => string (12 ) "602-312-4455" ["transactionDetails"] => Array (4) {["totalAmt"] => Zeichenfolge (6) "100.00" ["Währung"] => Zeichenfolge (3) "USD" [" Steuer "] => Zeichenfolge (4)" 5,00 "[" Versand "] => Zeichenfolge (4)" 5,00 "} [" Artikel "] => Objekt (stdClass) # 3 (3) {[" Name "] = > string (7) "T-Shirt" ["Farbe"] =>

und hier ist der Code, um ihn in einen String mit einem Zeilenumbruch für jeden Parameter zu analysieren:

function parseObj($obj, $prefix = ''){
    $stringRtrn = '';
    foreach($obj as $key=>$value){
        if($prefix){
            switch ($key) {
                case is_array($key):
                    foreach($key as $k=>$v){
                        $stringRtrn .= parseObj($key, $obj);
                    }
                    break;
                case is_object($key):
                    $stringRtrn .= parseObj($key, $obj);
                    break;
                default:
                    switch ($value) {
                        case is_array($value):
                            $stringRtrn .= parseObj($value, $key);
                            break;
                        case is_object($value):
                            $stringRtrn .= parseObj($value, $key);
                            break;
                        default:
                            $stringRtrn .= $prefix ."_". $key ." = ". $value ."<br>";
                            break;
                    }
                    break;
            }
        } else { // end if($prefix)
            switch($key){
                case is_array($key):
                    $stringRtrn .= parseObj($key, $obj);
                    break;
                case is_object($key):

                    $stringRtrn .= parseObj($key, $obj);
                    break;
                default:
                    switch ($value) {
                        case is_array($value):
                            $stringRtrn .= parseObj($value, $key);
                            break;
                        case is_object($value):
                            $stringRtrn .= parseObj($value, $key);
                            break;                      
                        default:
                            $stringRtrn .= $key ." = ". $value ."<br>";
                            break;
                    } // end inner switch 
            } // end outer switch
        } // end else
    } // end foreach($obj as $key=>$value)
    return $stringRtrn;
} // END parseObj()

Dadurch wird das Objekt wie folgt zurückgegeben:

shippingInfo_fName = Bill
shippingInfo_lName = Test
shippingInfo_address1 = 22 S. Deleware St.
shippingInfo_city = Chandler
shippingInfo_state = AZ
shippingInfo_zip = 85225
phone = 602-312-4455
transactionDetails_totalAmt = 100.00
transactionDetails_currency = USD
transactionDetails_tax = 5.00
transactionDetails_shipping = 5.00
item_name = T-shirt
item_color = blue
item_itemQty = 1

Ich habe die verschachtelten switch- Anweisungen ausgeführt, um Verwechslungen mit zu vermeiden if . . . ifelse . . . else, aber es war fast genauso lang. Wenn es hilft, fragen Sie einfach nach den if-Bedingungen und ich kann sie für diejenigen einfügen, die sie benötigen.

Answer 23

Das Durchlaufen eines Verzeichnisbaums ist ein gutes Beispiel. Sie können etwas Ähnliches tun, um ein Array zu verarbeiten. Hier ist eine wirklich einfache rekursive Funktion, die einfach eine Zeichenfolge, ein einfaches Array von Zeichenfolgen oder ein verschachteltes Array von Zeichenfolgen beliebiger Tiefe verarbeitet und Instanzen von 'Hallo' durch 'Auf Wiedersehen' in der Zeichenfolge oder den Werten des Arrays oder einer beliebigen Zeichenfolge ersetzt Unterarray:

function replaceHello($a) {
    if (! is_array($a)) {
        $a = str_replace('hello', 'goodbye', $a);
    } else {
        foreach($a as $key => $value) {
            $a[$key] = replaceHello($value);
        }
    }
    return $a
}

Es weiß, wann es beendet werden muss, da das "Ding", das es verarbeitet, irgendwann kein Array mehr ist. Wenn Sie beispielsweise replaceHello ('Hallo') aufrufen, wird 'Auf Wiedersehen' zurückgegeben. Wenn Sie ihm ein Array von Zeichenfolgen senden, obwohl es sich für jedes Mitglied des Arrays einmal selbst aufruft, geben Sie das verarbeitete Array zurück.

Answer 24

Wenn Sie Anthony Forloneys Beispiel einen bestimmten Wert hinzufügen (z. B. "1"), ist alles klar:

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

Original:

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

Answer 25

Wie hörst du damit auf?

Pathros

Answer 26

0

Dies ist ein sehr einfaches Beispiel für Fakultät mit Rekursion:

Fakultäten sind ein sehr einfaches mathematisches Konzept. Sie sind wie 5 geschrieben! und das bedeutet 5 * 4 * 3 * 2 * 1. Also 6! ist 720 und 4! ist 24.

function factorial($number) { 

    if ($number < 2) { 
        return 1; 
    } else { 
        return ($number * factorial($number-1)); 
    } 
}

Ich hoffe, das ist nützlich für Sie. :) :)

quelle

Wie hörst du damit auf?

Pathros

1

In Fakultät rufen wir kontinuierlich auf, bis das übergebene Argument 1 ist, und wenn Argument 1 ist, geben wir einfach 1 zurück, also stoppen Sie die Rekursion

Answer 27

Wie hörst du damit auf?

Pathros

Answer 28

1

In Fakultät rufen wir kontinuierlich auf, bis das übergebene Argument 1 ist, und wenn Argument 1 ist, geben wir einfach 1 zurück, also stoppen Sie die Rekursion

Answer 29

Es funktioniert ein einfaches Beispiel rekursiv (Y)

<?php 


function factorial($y,$x) { 

    if ($y < $x) { 
        echo $y; 
    } else { 
        echo $x; 
        factorial($y,$x+1);
    } 
}

$y=10;

$x=0;
factorial($y,$x);

 ?>

Answer 30

Rekursion für Kaprekars Konstante

function KaprekarsConstant($num, $count = 1) {
    $input = str_split($num);
    sort($input);

    $ascendingInput  = implode($input);
    $descendingInput = implode(array_reverse($input));

    $result = $ascendingInput > $descendingInput 
        ? $ascendingInput - $descendingInput 
        : $descendingInput - $ascendingInput;

    if ($result != 6174) {
        return KaprekarsConstant(sprintf('%04d', $result), $count + 1);
    }

    return $count;

}}

Die Funktion ruft sich mit dem Ergebnis der Berechnung so lange auf, bis sie die Kaprekars-Konstante erreicht, und gibt die Häufigkeit zurück, mit der die Berechnungen durchgeführt wurden.

/ edit Für alle, die Kaprekars Constant nicht kennen, ist eine Eingabe von 4 Ziffern mit mindestens zwei unterschiedlichen Ziffern erforderlich.

Was für Laien eine rekursive Funktion ist, die PHP verwendet

Antworten:

Laienbegriffe:

Etwas ausführlicher:

(20.04.10) Update: