Welche Probleme kann ich mit Rekursion lösen?

Question

Heute habe ich eine Methode mit Rekursion in PHP erstellt und interessiere mich dafür. Welche Probleme kann Rekursion tatsächlich lösen? Für welche Dinge können wir Rekursion verwenden?

Ich begann, es im Web zu suchen und suchen und suchen, aber ich kann nichts finden.

Also frage ich, was können wir tun mit der Verwendung von Rekursion?

Gibt es einige Einschränkungen? Dinge, die wir nicht mit Rekursion tun können, aber mit Standard-Schleifen können wir? Ich frage mich, ob ich Rekursion normalerweise in meinem Code sehr oft verwenden könnte.

Answer 1

Jede Art von Iteration durch irgendeine Datenstruktur kann mit Rekursion durchgeführt werden.

function factorial($n) { 
    $result = $n < 0 ? -1 : 1; 
    for($i = abs($n), $i > 1; $i--) { 
    $result *= $i; 
    } 
    return $result; 
} 

kann geschrieben werden:

function factorial($n) { 
    $forHelper = function($result, $i) { 
    return $i === 1 ? $result : $forHelper($result * $i, $i - 1); 
    } 
    return $forHelper($n < 0 ? -1 : 1, abs($n)); 
} 

Rekursion Dies nennt man Schwanz In der Tat kann man jede Schleife wie for, while, do while, foreach, etc so einfach Rekursion ersetzen konstruieren. In einigen Sprachen erzeugen die beiden obigen einen sehr ähnlichen Laufzeitcode, aber nicht PHP. Es verwendet für jeden Anruf etwas Speicher. Für mich sind beide gleichermaßen lesbar, aber ich wette, die meisten Programmierer würden es einfacher mit der Schleife finden, besonders wenn sie verschachtelt wird.

Einige Algorithmen, wo Sie eine Grafik oder Baum iterieren eine einfachere Version haben Rekursion anstatt Iteration:

function treeDepth($node) { 
    if($node === null) { 
    return 0; 
    } else { 
    return 1 + max(treeDepth($node->left), treeDepth($node->right)); 
    } 
} 

Eine hier iterative Lösung eine gewisse Art und Weise der Verfolgung der Orte, braucht es brauchen würde, zu besuchen und Sie führen also einen gewissen Verwaltungsaufwand aus, der von der rekursiven Version automatisch behandelt wird.

function treeDepth($node) { 
    $max = 0; 
    $backtrack = [[0, $node]]; 
    while(count($backtrack)) { 
    list($depth, $node) = array_pop($backtrack); 
    while($node !== null) { 
     array_push($backtrack, [++$depth, $node->right]); 
     $node = $node->left; 
    } 
    $max = max($max, $depth); 
    } 
    return $max; 
} 

Die Beschränkung hängt von der Sprache ab. In PHP wird für jeden Aufrufrahmen, der nicht für eine einfache Schleife reserviert ist, etwas Speicher reserviert. Das Node-Traversal verwendet immer Speicher, da der Prozess von Natur aus rekursiv ist.

Letztendlich sollten Sie so programmieren, dass Ihr Code so klar wie möglich ist, ohne an Optimierung zu denken. Verwenden Sie Schleifenkonstrukte dort, wo sie am klarsten sind und Rekursion dort, wo sie am klarsten ist. Nur wenn Sie tatsächlich auf Leistungsprobleme stossen, sollten Sie die Teile, die am meisten Zeit verbrauchen, profilieren und neu schreiben. Ich verwende den ursprünglichen Code als Kommentar, wenn er kurz ist und dokumentiert, was in der komplexeren iterativen Version tatsächlich passiert. In PHP-Funktionen sind Anrufe selbst teuer.

Answer 2

Was können wir mit Rekursion machen?

Lösen von rekursiven Problemen. Das Eltern-Kind-Problem, bei dem jedes Kind selbst wieder ein Elternteil sein kann, ist meistens das eine.

function doSomethingWithNode($node) 
{ 
    // Do something with $node 

    // Loop over all childs, and run this code for those childs too, and for those childs, and for those childs, and ... 
    foreach($node->getChilds() as $child) { 
     doSomethingWithNode($child); 
    } 
} 

doSomethingWithNode($rootNode); 

Gibt es einige Einschränkungen?

Ja. PHP (und andere Programmiersprachen) verfolgt, welcher Code welche Funktion aufruft, damit er weiß, wo er nach der Rückkehr der Funktion weitermachen soll. Dies wird call stack genannt. Das Hinzufügen von neuen Einträgen zu call stack dauert etwas Speicher und einige Zeit. Hauptsächlich das erste CAN führt zu Problemen, wenn Sie viele (Millionen) Iterationen haben.

Abhängig von Ihrer Installation kann die call stack sogar begrenzt sein. Standardmäßig ist es nicht. Durch die Installation der xdebug -Erweiterung gibt es maximal 100 verschachtelte Aufrufe (standardmäßig kann in der Konfig geändert werden). Bei diesen Einstellungen führt dies zu einem schwerwiegenden Fehler (example).

Dinge, die wir nicht mit Rekursion tun können, aber mit Standard-Schleifen können wir? Ich frage mich, ob ich jetzt Rekursion normalerweise in meinem Code verwenden könnte sehr oft

Aufgrund der oben genannten Einschränkungen sollte Rekursion mit Vorsicht verwendet werden. Wenn Sie es mit einer normalen while oder for-Schleife lösen können: Verwenden Sie die normale Schleife. Die meiste Zeit wird es dazu führen, dass Code leichter zu lesen ist.

Wenn Sie sich für die Portabilität interessieren (zum Beispiel beim Schreiben eines Open-Source-Projekts), möchten Sie wahrscheinlich xdebug-Benutzer berücksichtigen.