PHP Master | Rekursion verstehen

Kernpunkte

• Rekursion ist eine Methode zur Problemlösung, bei der die Funktion direkt oder indirekt (über eine Funktionsaufrufschleife) aufgerufen wird. Es ist besonders nützlich, wenn es darum geht, durch Bäume und Listen zu iterieren oder die meisten O -Sorten von O (n log n) durchzuführen.
• rekursive Funktionen müssen eine Basisfall- oder Schutzklausel haben, um zu verhindern, dass sie sich unendlich anrufen, was zu einem Stapelüberlauffehler führt. Dieses Basisbeispiel ist eine Bedingung, die verhindert, dass die Funktion weitere rekursive Anrufe tätigt, wenn eine bestimmte Bedingung erfüllt ist.
• Es gibt zwei Arten von Rekursion: direkte Rekursion und indirekte Rekursion. Direkte Rekursion bedeutet, dass sich die Funktion direkt aufruft, während die indirekte Rekursion bedeutet, dass die Funktion sich indirekt durch eine andere Funktion aufruft. Dieser Artikel konzentriert sich auf die direkte Rekursion.
• Während Rekursion ein leistungsstarkes Werkzeug sein kann, muss es mit Vorsicht verwendet werden. PHP optimiert rekursive Funktionen nicht und sie sind normalerweise nicht so effizient und schnell wie ihre iterativen Gegenstücke. Die Rekursion kann jedoch in einigen Fällen effizienter sein, z.

In einem früheren Beitrag habe ich über Iteratoren geschrieben und wie man sie benutzt. Heute möchte ich die iterativen Geschwister sehen: Rekursion. Bevor wir jedoch über die Überarbeitung diskutieren, werfen wir einen Blick auf diesen Code:

<?php
function factorial($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    $factorial = 1; 
    while ($number > 0) {
        $factorial *= $number;
        $number--;
    }
    return $factorial;
}

Fabriken sind das Ergebnis einer Zahl, die von allen positiven Ganzzahlen multipliziert wird, die kleiner als diese Zahl ist. Schreiben wir jetzt dieses Beispiel wie folgt um:

<?php
function factorial_recursive($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    if ($number == 0) {
        return 1;
    }
    return $number * factorial_recursive($number - 1);
}

Wenn wir diese beiden Funktionen nennen, erhalten wir das gleiche Ergebnis, aber beachten Sie, dass die zweite Funktion das Faktor berechnet, indem Sie sich selbst anrufen. Dies wird als Rekursion bezeichnet.

Was ist Rekursion?

rekursive Funktionen beziehen sich auf Funktionen, die sich direkt oder über Funktionsaufrufe aufrufen. Rekursion kann auch auf eine Methode zur Problemlösung verweisen, die zuerst eine kleinere Version des Problems löst und dann dieses Ergebnis verwendet, um einige andere Berechnungen hinzuzufügen, um eine Antwort auf die ursprüngliche Frage zu bilden. In der Regel löst dieser Ansatz bei der Lösung kleinerer Versionen kleinere Versionen des Puzzles und so weiter, bis ein leicht lösliches "Basisbeispiel" erreicht ist. Um eine rekursive Funktion zu schreiben, müssen Sie sie mit einer Rückgabemethode zur Verfügung stellen. Andernfalls ruft sie sich immer wieder für immer an (oder bis der Anrufstapel, das Skript abgestimmt oder der Speicher ausgeführt wird). Dies wird als Schutzklausel oder Basisfall bezeichnet. Die einfachste Form einer rekursiven Funktion ist wie folgt:

<?php
function my_recursive_func(args) {
    if (simplest case) {
        // 停止函数无限运行的基例/保护子句
        return simple value;
    }
    else {
        // 使用更简单的参数再次调用函数
        my_recursive_func(argsSimplified);
    }
}

rekursives Typ

Wenn sich eine Funktion direkt aufruft, wird sie als direkte Rekursion bezeichnet. Der letzte Aufruf einer Funktion in einer Funktionsaufrufschleife wird als indirekte Rekursion bezeichnet. Bitte überprüfen Sie das folgende Beispiel für die indirekte Rekursion:

<?php
function A($num) {
    $num -= 1;
    if($num > 0) {  
        echo "A is Calling B($num)\n";
        $num = B($num);
    }
    return $num;
}

function B($num) {
    $num -= 2;
    if($num > 0) {
        echo "B is Calling A($num)\n";
        $num = A($num);
    }
    return $num;
}

$num = 4;
echo "Calling A($num)\n";
echo 'Result: ' . A($num);

<code>Calling A(4)
A is Calling B(3)
B is Calling A(1)
Result: 0</code>

Das obige Beispiel ist tatsächlich nutzloser Code, um Ihnen zu zeigen, wie sich eine Funktion durch eine andere Funktion indirekt aufruft. Das Aufrufen von A (N & gt; 4) oder B (N & gt; 4) führt zu einer Funktion, die aus einem anderen Funktionsaufruf bezeichnet wird. Es ist wichtig zu wissen, dass sich Funktionen indirekt so nennen können, aber in diesem Artikel befassen wir uns nur mit direkter Rekursion.

Ein praktisches Beispiel

Um Ihnen die Kraft der Rekursion anzuzeigen, werden wir eine Funktion schreiben, die nach Schlüssel in einem Array sucht und die Ergebnisse zurückgibt.

<?php
function factorial($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    $factorial = 1; 
    while ($number > 0) {
        $factorial *= $number;
        $number--;
    }
    return $factorial;
}

<?php
function factorial_recursive($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    if ($number == 0) {
        return 1;
    }
    return $number * factorial_recursive($number - 1);
}

Alles verlief reibungslos, aber beachten Sie, dass wir nur in die zweite Schicht des Arrays iteriert wurden, sodass die Suche nach "Fibonacci" in der dritten Schicht fehlschlug. Wenn wir nach Arrays unsicherer Tiefe suchen würden, würde dies nicht ausreichen. Wir können die Suche als rekursive Funktion umschreiben:

<?php
function my_recursive_func(args) {
    if (simplest case) {
        // 停止函数无限运行的基例/保护子句
        return simple value;
    }
    else {
        // 使用更简单的参数再次调用函数
        my_recursive_func(argsSimplified);
    }
}

Mit rekursiven Funktionen können wir mehrere Ebenen von tiefen Arrays durchsuchen, da wir nicht die Tiefe der hartcodierten Funktionen haben. Es läuft einfach weiter, bis alle Werte im Array durchlaufen werden.

Kopfrekursion und Schwanzrekursion

In all unseren bisherigen Beispielen haben wir eine sogenannte Header-Rekursion verwendet. Wenn sich eine Funktion aufruft, wartet sie auf das Ergebnis aus dem Anruf, bevor sie ihren eigenen Wert zurückgibt. Sie können eine Funktion schreiben, die nicht mit dem Rückgabewert arbeitet, sondern alle erforderlichen Werte als Parameter übergibt. Dies wird als Schwanzaufruf (oder Schwanzrekursion) bezeichnet. Diese Methode wird normalerweise bevorzugt, da die Laufzeit der Sprache manchmal Anrufe optimieren kann. Daher besteht keine Gefahr, den Anrufstapel zu sprengen, aber PHP tut dies nicht. Das Folgende ist unser faktorielles Beispiel, das so geändert wird, dass ein Schwanzanruf getätigt wird. Beachten Sie, dass das Ergebnis des rekursiven Anrufs zurückgegeben wird, anstatt ihn weiter zu manipulieren.

<?php
function A($num) {
    $num -= 1;
    if($num > 0) {  
        echo "A is Calling B($num)\n";
        $num = B($num);
    }
    return $num;
}

function B($num) {
    $num -= 2;
    if($num > 0) {
        echo "B is Calling A($num)\n";
        $num = A($num);
    }
    return $num;
}

$num = 4;
echo "Calling A($num)\n";
echo 'Result: ' . A($num);

Allgemeine Vorschläge

Jeder Code, in dem iterativ geschrieben werden kann, kann rekursiv geschrieben werden. Dies ist jedoch nicht immer einfach (sogar weise). Die Rekursion ist ausgezeichnet, wenn es darum geht, durch Bäume und Listen zu iterieren oder die meisten O -Sorten von O (n log n) durchzuführen. Rekursion ist besser geeignet als iterative Methoden, wenn Sie sich wiederholte Probleme dividieren müssen, z. Rekursion funktioniert gut, wenn Sie unsichere Tiefen durchqueren. Denken Sie daran, dass PHP rekursive Funktionen nicht optimiert, und selbst wenn Sie sie für Schwanzanrufe schreiben, sind rekursive Funktionen normalerweise ineffizient und langsamer als ihre iterativen Gegenstücke, obwohl sie den Job manchmal besser machen, wie im obigen Code -Beispiel. Rekursion ist normalerweise die bevorzugte Alternative zur Iteration in der funktionalen Programmierung, sodass die meisten funktionalen Sprachen rekursive Funktionen optimieren. Wenn Sie XDEBUG verwenden, überprüfen Sie die Konfiguration Ihres Systems. Standardmäßig begrenzen Sie 100 rekursive Anrufe, und wenn Sie dieses Grenze überschreiten, wird Ihr Skript ein Fehler "maximaler Verschachtelungsgrenze" geworfen. Wenn Sie diese Einstellung ändern müssen, können Sie den Konfigurationswert debug.max_nesting_level aktualisieren. Schließlich ist es am besten, die Erklärung von Stapelhaufen und Rekursion zu lesen, wodurch der Stapelüberlauf versteht, wie er den Stapel während der Rekursion nennt.

Schlussfolgerung

In diesem Artikel stelle ich Ihnen intensiv die Rekursion und den Vergleich mit der Iteration vor. Ich habe Ihnen auch gezeigt, wie Sie rekursive Funktionen schreiben, wann Sie sie schreiben und warum. Ich versuche auch, Sie vor einigen Fallstricken zu warnen, denen Sie bei der Verwendung von Rekursion möglicherweise begegnen könnten. Rekursion ist so, selbst viele erfahrene Programmierer verwenden sie jahrelang nicht, und viele andere haben noch nie davon gehört, was eine Schande ist, weil es ein wirklich mächtiges Konzept ist. Ich hoffe, dass ich Ihnen durch diesen Beitrag genügend Wissen geben kann, um Ihre eigenen rekursiven Funktionen zu schreiben. Aber denken Sie daran, dass Sie dieses Werkzeug immer mit Vorsicht verwenden müssen.

Bild von Alexandre Duret-Lutz von Flickr

FAQs zum Verständnis der Rekursion in PHP (FAQ)

Was ist das Basisbeispiel in der rekursiven PHP -Funktion?

Das grundlegende Beispiel in rekursiven PHP -Funktionen ist eine Bedingung, die verhindert, dass die Funktion sich unendlich aufruft. Es ist ein wesentlicher Bestandteil jeder rekursiven Funktion. Ohne Basisfall nennt sich die rekursive Funktion unendlich, was zu einem Stapelüberlauffehler führt. In PHP werden grundlegende Beispiele normalerweise unter Verwendung der Anweisung "If" zu Beginn einer Funktion definiert. Die Funktion überprüft diese Bedingung, bevor er mit dem rekursiven Aufruf fortgesetzt wird. Wenn die Bedingung erfüllt ist, gibt die Funktion einen Wert zurück und hört auf, sich selbst anzurufen.

Wie funktionieren rekursive Funktionen in PHP?

Die rekursive Funktion in PHP ruft sich in seiner eigenen Funktionskörper auf, bis eine bestimmte Erkrankung, die als Basisfall bezeichnet wird, erfüllt ist. Wenn eine rekursive Funktion aufgerufen wird, führt sie eine bestimmte Aufgabe aus und ruft sich dann auf, um die Aufgabe zu wiederholen. Dieser Vorgang wird fortgesetzt, bis der Basisfall erfüllt ist und die Funktion nicht mehr selbst aufgerufen wird. Jedes Mal, wenn eine Funktion aufgerufen wird, wird auf dem Anrufstapel eine neue Ebene erstellt, wodurch die Variablen gespeichert und Adressen der Funktionsaufrufe zurückgegeben werden. Sobald der Basisfall erfüllt ist, wird die Funktion zurückgekehrt und die Anrufstapelschicht für Schicht entlüftet.

Können alle Probleme im PHP unter Verwendung von Rekursion gelöst werden?

Während Rekursion ein leistungsstarkes Werkzeug in PHP sein kann, können oder sollten nicht alle Probleme unter Verwendung einer Rekursion gelöst werden. Die Rekursion eignet sich am besten für Probleme, die in kleinere, ähnliche Probleme unterteilt werden können, z. Wenn sie jedoch nicht ordnungsgemäß verwendet werden, kann Rekursion zu hohen Speicherverwendungen und Stapelüberlauffehlern führen. Es ist auch in der Regel langsamer als iterative Lösungen aufgrund des Overhead von Funktionsaufrufen. Daher ist es sehr wichtig, das vorliegende Problem zu verstehen und den richtigen Ansatz zu wählen.

Wie kann man einen Stapelüberlauf in rekursiven PHP -Funktionen verhindern?

Stapelüberlauf in rekursiven Funktionen können verhindert werden, indem die Basisfälle sorgfältig definiert werden, die die Funktion letztendlich erreichen wird. Der Basisfall ist eine Bedingung, und wenn diese Bedingung erfüllt ist, hört die Funktion auf, weitere rekursive Anrufe zu tätigen. Ohne Basisfall nennt sich die Funktion unendlich und führt zu einem Stapelüberlauf. Es ist auch wichtig sicherzustellen, dass jeder rekursive Aufruf die Funktion näher an den Basisfall bringt, um eine unendliche Rekursion zu vermeiden.

Was ist die Schwanzrekursion in PHP?

Schwanzrekursion ist eine spezielle Art von Rekursion, bei der der rekursive Anruf die letzte Operation in der Funktion ist. Dies bedeutet, dass frühere Funktionsaufrufe nicht im Auge behalten müssen, sodass der Compiler oder Interpreter die Rekursion optimieren und das Risiko eines Stapelüberlaufs verringern kann. PHP selbst unterstützt jedoch keine rekursive Schwanzoptimierung. Während Sie also Schwanz rekursive Funktionen in PHP schreiben können, sind sie nicht optimiert und verbrauchen immer noch Stapelraum für jeden rekursiven Anruf.

Wie vergleicht man die Rekursion mit der Schleife in PHP?

sowohl Rekursion als auch Schleifen können verwendet werden, um eine Reihe von Anweisungen in PHP zu wiederholen. Sie arbeiten jedoch unterschiedlich und haben unterschiedliche Vor- und Nachteile. Rekursion ist ein leistungsstarkes Werkzeug zur Lösung komplexer Probleme, die in kleinere, ähnliche Probleme unterteilt werden können. Es ist besonders nützlich, um Aufgaben wie Bäume oder Grafiken zu durchqueren. Schleifen hingegen sind oft besser geeignet für einfache sich wiederholende Aufgaben. Sie verwenden weniger Speicher als Rekursion und es ist unwahrscheinlich, dass sie einen Stapelüberlauf verursachen.

Kann ich Rekursion verwenden, um über Arrays in PHP zu iterieren?

Ja, Rekursion kann ein sehr effektiver Weg sein, um Arrays (insbesondere mehrdimensionale Arrays) in PHP zu durchqueren. Sie können eine rekursive Funktion verwenden, um über jedes Element in einem Array zu iterieren, und wenn das Element selbst ein Array ist, kann sich die Funktion aufrufen, um über das Array zu iterieren. Dieser Prozess wird fortgesetzt, bis auf alle Elemente zugegriffen wird. Denken Sie jedoch daran, dass die Rekursion langsamer sein kann als iterative Lösungen und mehr Speicher, insbesondere bei großen Arrays.

Was ist gegenseitige Rekursion in PHP?

gegenseitige Rekursion bezieht sich auf zwei oder mehr Funktionen, die in einer Schleife miteinander aufgerufen werden. In PHP bedeutet dies, dass die Funktion A Funktion B und Funktion B aufruft Funktion A. Dies kann ein leistungsstarkes Instrument zur Lösung bestimmter Arten von Problemen sein, aber es kann auch schwieriger zu verstehen und zu debuggen als einfache Rekursion. Wie bei jeder rekursiven Funktion ist es wichtig, einen Basisfall zu definieren, um die unendliche Rekursion zu verhindern.

Wie kann rekursive Funktionen in PHP debuggen?

Debugging rekursive Funktionen in PHP kann eine Herausforderung sein, da sich die Funktion mehrmals aufruft. Es gibt jedoch mehrere Strategien, die Sie anwenden können. Eine Möglichkeit besteht darin, eine Druckanweisung oder einen Debugger zu verwenden, um den Funktionsaufruf zu verfolgen und den Status der Variablen in jedem Schritt anzuzeigen. Eine andere Möglichkeit besteht darin, einen rekursiven Baum zu zeichnen, um Funktionsaufrufe zu visualisieren. Es ist auch wichtig, den Basisfall und den Rekursionsfall zu überprüfen, um sicherzustellen, dass sie korrekt sind.

Was sind die Einschränkungen bei der Verwendung von Rekursion in PHP?

Während Rekursion ein leistungsstarkes Werkzeug in PHP sein kann, hat es einige Einschränkungen. Eine der Hauptbeschränkungen ist, dass, wenn die Rekursion zu tief ist, das Risiko eines Stapelüberlaufs besteht. Dies liegt daran, dass jeder rekursive Anruf dem Anrufstapel eine neue Ebene hinzufügt und die Stapelgröße begrenzt ist. Aufgrund des Overhead von Funktionsaufrufen kann die Rekursion auch langsamer sein als iterative Lösungen und wird mehr Speicher verwenden. Darüber hinaus können rekursive Funktionen schwerer zu verstehen und zu debuggen als iterative Lösungen.

Das obige ist der detaillierte Inhalt vonPHP Master | Rekursion verstehen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!