webentwicklung-frage-antwort-db.com.de

Was für Laien eine rekursive Funktion ist PHP

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 hat mich total verloren!

Vielen Dank im Voraus; -) Wie oft setzen Sie sie auch in der Webentwicklung ein?

70
Imran

Laienbegriffe:

Eine rekursive Funktion ist eine Funktion, die selbst aufruft. 

Ein bisschen mehr in die Tiefe:

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

Was für mich ein gutes Lernbeispiel war, da ich über ein solides Grundwissen in Mathematik verfügte, war factorial . Nach den Kommentaren scheint die faktorielle Funktion etwas zu viel zu sein. Ich lass 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 nicht persönlich auf rekursive Aufrufe zurück. Nicht dass ich es als schlechte Praxis bezeichnen würde, auf Rekursion zu setzen, aber sie sollten nicht Ihre erste Option sein. Sie können tödlich sein, wenn sie nicht ordnungsgemäß verwendet werden.

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

(20.04.10) Update:

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

87

Ein Beispiel wäre, jede Datei in einem Unterverzeichnis eines bestimmten Verzeichnisses zu drucken (wenn Sie keine Symlinks in diesen Verzeichnissen haben, die die Funktion irgendwie beschädigen 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 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, müssen Sie nach den speziellen Verzeichnissen . und .. suchen. Andernfalls bleiben Sie ständig beim Aufruf von printAllFiles("."). Außerdem müssen Sie prüfen, was gedruckt werden soll und wie Ihr aktuelles Arbeitsverzeichnis ist (siehe opendir(), getcwd(), ...).

30
Progman

Rekursion ist etwas, das sich wiederholt. Wie eine Funktion, die sich aus sich selbst heraus ruft. Lassen Sie mich in einem etwas Pseudo-Beispiel zeigen:

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

An der Bar angekommen, 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 :(
    }
}

Nun wollen wir nur hoffen, 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 die Rekursion ab.

22
Freyr

Es ist eine Funktion, die sich selbst nennt. Es ist nützlich, um bestimmte Datenstrukturen zu durchlaufen, die sich wiederholen, beispielsweise 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.

    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 der rechten Seite.

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--;
}

Zum Schluss 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 durchzugehen. 

9
James Westgate

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

7
Samuel

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

funktion category_tree ($ parent = 0, $ sep = '') 
 {
 $ q = "id, name aus categorye auswählen, wobei parent_id =". $ parent; 
 $ rs = mysql_query ($ q); 
 while ($ rd = mysql_fetch_object ($ rs)) 
 {
 echo ('id.' ">". $ sep. $ rd-> name. ''); 
 category_tree ($ rd-> id, $ sep. '-'); 
}. }
5
Imran Naqvi

Rekursion ist eine schicke Art zu sagen: "Mach das Ding wieder, bis es fertig ist".

Zwei wichtige Dinge zu haben: 

  1. Ein Basisfall - Sie müssen ein Ziel erreichen.
  2. Ein Test - Wie können Sie feststellen, ob Sie das Ziel erreicht haben?.

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 nehmen und zu sortieren. Nun kommt der rekursive Teil: Gibt es mehr Bücher? Wenn ja, mach es nochmal. Das "Wiederholen" ist die Rekursion. Das "gibt es noch mehr Bücher" ist der Test. Und "nein, keine Bücher mehr" ist der Basisfall.

4
Shane Castle

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

Weil es eine Sache ist:

Die Funktion, wenn die aufgerufene Funktion im Speicher erstellt wird (neue Instanz wird erstellt)

Die rekursive Funktion IS CALLLING ITSELF NICHT, sondern ihre aufrufende andere Instanz - es ist also keine Funktion im Speicher, die etwas Magie ausübt. Seine paar Instanzen im Speicher, die sich selbst einige Werte zurückgeben - und dieses Verhalten ist das gleiche, wenn zum Beispiel die Funktion a die 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 ist sinnvoll.

2
Ales

Im Grunde das. Es ruft sich selbst 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 es auch googeln. Beachten Sie das "Haben Sie gemeint" (klicken Sie darauf ...). http://www.google.com/search?q=recursion&spell=1

1
user34537

Rekursion ist eine Alternative zu Schleifen. Es ist selten, dass sie dem Code mehr Klarheit oder Eleganz verleihen. Ein gutes Beispiel ist die Antwort von Progman. Wenn er keine Rekursion verwenden würde, müsste er nachverfolgen, in welchem ​​Verzeichnis er sich derzeit befindet (dies wird als Status bezeichnet). Rekursionen ermöglichen es ihm, die Buchhaltung über den Stack (den Bereich, in dem Variablen enthalten sind) durchzuführen und Rücksprungadresse einer Methode werden gespeichert)

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

1
stacker

Hier ist ein praktisches Beispiel (es gibt bereits einige gute). Ich wollte nur einen hinzufügen, der für fast alle Entwickler nützlich ist.

Zu einem bestimmten Zeitpunkt müssen Entwickler ein Objekt so analysieren, wie es mit einer Antwort von einer API oder einem Objekt- oder Array-Typ beantwortet wird.

Diese Funktion wird anfangs aufgerufen, um ein Objekt zu analysieren, das nur Parameter enthalten kann. Was aber, wenn das Objekt auch andere Objekte oder Arrays enthält? Dies muss angesprochen werden, und in der Regel erledigt dies bereits die grundlegende Funktion. Daher ruft sich die Funktion erneut auf (nachdem bestätigt wurde, dass der Schlüssel oder Wert entweder ein Objekt oder ein Array ist) und analysiert dieses neue Objekt oder Array. Letztendlich wird ein String zurückgegeben, der jeden Parameter in einer eigenen Zeile zur besseren Lesbarkeit erstellt. Sie können die Werte jedoch genauso einfach in einer Protokolldatei protokollieren oder in eine DB oder in ein beliebiges anderes einfügen.

Ich habe den Parameter $prefix hinzugefügt, um das übergeordnete Element zu verwenden, um die Endvariable zu beschreiben, damit wir sehen können, worauf sich der Wert bezieht. Es enthält keine Elemente wie Nullwerte, dies kann jedoch anhand dieses Beispiels 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:

object (stdClass) # 1 (4) {["shippingInfo"] => object (stdClass) # 2 (6) {["fName"] => string (4) "bill" ["lName"] => string ( 4) "Test" ["address1"] => 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"] => string (6) "100.00" ["currency"] => string (3) "USD" [" tax "] => string (4)" 5.00 "[" shipping "] => string (4)" 5.00 "} [" item "] => object (stdClass) # 3 (3) {[" name "] = > string (7) "T-Shirt" ["color"] => string (4) "blue" ["itemQty"] => int (1)}}

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

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()

Das Objekt wird 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 geschachtelten switch - Anweisungen gemacht, um Verwechslungen mit if . . . ifelse . . . else zu vermeiden, 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.

1
Joel

Wenn Sie dem Beispiel von Anthony Forloney einen bestimmten Wert hinzufügen (beispielsweise "1"), wäre 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.
  }
}
0
Kevin

Ich finde die Beispiele auch nicht hilfreich. Sie können nicht zwei Probleme gleichzeitig lösen, wenn Mathematik involviert ist und Ihr Geist zwischen zwei Problemen hin und her wechselt. Genug geredet

Beispiel:

Ich habe eine Funktion, bei der ich Strings in ein Array auf der Basis von : Trennzeichen auflöst.

public function explodeString($string)
{
  return explode(":", $string);
}

Ich habe eine andere Funktion, bei der ich Strings als Eingabe nehme

public function doRec()
{
    $strings = [
        'no:go',
        'hello:world',
        'nested' => [
            'iam:good',
            'bad:array',
            'bad:how',
            'bad:about',
        ]
    ];

    $response = [];

    foreach ($strings as $string) {
        array_Push($response,$this->explodeString($string));
    }

    return $response;
}

Das Problem ist, meine Eingabe hat ein verschachteltes Array und meine explodeString-Funktion erhält einen Typ string. Ich kann etwas Code in explodeString-Funktion umschreiben, um mich daran anzupassen, aber ich brauche immer noch dieselbe Funktion, um dieselbe Operation an meinem String durchzuführen. Dort kann ich die Methode recursively aufrufen. Hier ist also die endgültige explodeString-Funktion mit Rekursion.

public function explodeString($string)
{
    if (is_array($string)) {
       $combine = [];
       foreach ($string as $str) {
           array_Push($combine, $this->explodeString($str));
        }
       return $combine;
    }

    return explode(":", $string);
}
0
Faiz Khan

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 selbst mit dem Ergebnis der Berechnung auf, bis sie die Kaprekars-Konstante erreicht, bei der die Anzahl der Berechnungen zurückgegeben wird.

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

0
Bart

Ein gutes Beispiel dafür ist ein Verzeichnisbaum. Sie können etwas Ähnliches tun, um ein Array zu verarbeiten. Hier ist eine wirklich einfache rekursive Funktion, die einfach einen String, ein einfaches String-Array oder ein verschachteltes String-Array mit beliebiger Tiefe verarbeitet und Instanzen von 'Hallo' durch 'Goodbye' im String oder die Werte des Arrays oder eines beliebigen anderen Objekts ersetzt Unterfeld: 

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 zu beenden ist, weil das "Ding", das es verarbeitet, zu einem bestimmten Zeitpunkt kein Array ist. Wenn Sie beispielsweise replaceHello ('Hallo') anrufen, wird 'Auf Wiedersehen' zurückgegeben. Wenn Sie ein Array von Zeichenfolgen senden, wird es sich selbst einmal für jedes Mitglied des Arrays aufrufen und das verarbeitete Array zurückgeben.

0
Bob Ray

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

Faktoren 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)); 
    } 
}

hoffe das ist nützlich für dich. :)

0
user4614642

Es funktioniert ein rekursives Beispiel (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);

 ?>
0