Mir fällt es sehr schwer zu verstehen, wie man rekursiv über Probleme nachdenkt und sie mit Haskell löst. Ich habe Stunden damit verbracht, zu lesen, um meinen Kopf in die Rekursion zu stecken. Die Erklärung, die ich am häufigsten von Leuten bekomme, die es verstehen, ist nie klar und ist etwas wie "Du gibst eine Funktion, den Namen der Funktion als Argument, die Funktion wird dann ausgeführt, löst ein kleines Stück des Problems und ruft die Funktion immer wieder, bis Sie den Basisfall treffen ".
Kann jemand bitte freundlich genug sein und mich durch den Gedankenprozess dieser drei einfachen rekursiven Funktionen führen? Nicht so sehr die Funktionalität von ihnen, sondern wie der Code letztendlich ausgeführt wird und das Problem rekursiv löst.
Vielen Dank im Voraus!
Funktion 1
%Vor%Funktion 2
%Vor%Funktion 3
%Vor%Wenn Sie versuchen, die Rekursion zu verstehen, können Sie leichter darüber nachdenken, wie sich der Algorithmus für eine gegebene Eingabe verhält. Es ist einfach, sich auf den Ausführungsweg festzulegen, also stellen Sie sich stattdessen Fragen wie:
Oder für Rekursion auf Zahlen:
Die Struktur eines rekursiven Algorithmus ist oft nur eine Frage der obigen Fälle. Sehen wir uns an, wie sich Ihre Algorithmen verhalten, um ein Gefühl für diesen Ansatz zu bekommen:
Wie Sie sehen können, ist das einzige interessante Verhalten # 3. Die anderen stellen nur sicher, dass der Algorithmus beendet wird. Blick auf die Definition,
%Vor% Das Aufrufen von [1, 2] wird zu:
maximum' funktioniert, indem eine Zahl zurückgegeben wird, die in diesem Fall rekursiv mit max verarbeitet werden kann. Schauen wir uns einen weiteren Fall an:
Sie können sehen, wie für diese Eingabe der rekursive Aufruf von maximum' in der ersten Zeile genau dem vorherigen Beispiel entspricht.
Umkehren funktioniert, indem man den Kopf der gegebenen Liste nimmt und am Ende klebt. Für eine leere Liste bedeutet dies keine Arbeit, das ist der Grundfall. Also angesichts der Definition:
%Vor% Lass uns etwas ersetzen. Da [x] äquivalent zu x:[] ist, können Sie sehen, dass es tatsächlich zwei Werte gibt:
Einfach genug. Und für eine Zwei-Elemente-Liste:
%Vor%Diese Funktion führt eine Rekursion über ein Integer-Argument sowie Listen ein, also gibt es zwei Basisfälle.
Was passiert, wenn wir 0 oder weniger Gegenstände nehmen? Wir müssen keine Gegenstände nehmen, also geben Sie einfach die leere Liste zurück.
%Vor%Was passiert, wenn wir eine leere Liste übergeben? Es gibt keine weiteren Elemente mehr, also stoppen Sie die Rekursion.
%Vor%Der Kern des Algorithmus besteht eigentlich darin, die Liste zu durchlaufen, die Eingabeliste auseinander zu ziehen und die Anzahl der Elemente zu verringern, bis einer der obigen Basisfälle den Prozess stoppt.
%Vor%Also, in dem Fall, in dem der numerische Grundfall zuerst erfüllt ist, hören wir auf, bevor wir das Ende der Liste erreichen.
%Vor%In dem Fall, in dem der Listenbasisfall zuerst erfüllt wird, haben wir keine Elemente mehr, bevor der Zähler 0 erreicht, und geben einfach zurück, was wir können.
%Vor%Sie fragen nach "Gedankenprozess", vermutlich von einem Programmierer, nicht von einem Computer, richtig? Also hier sind meine zwei Cent:
Wenn Sie eine Funktion g mit Rekursion schreiben möchten, denken Sie daran, imagine das Sie haben diese Funktion bereits geschrieben Das ist alles.
Das heißt, Sie können es verwenden, wann immer Sie es brauchen, und es wird "tun" was auch immer es tun soll. Schreiben Sie einfach auf, was das ist - formulieren Sie die Gesetze , die es befolgen muss , schreiben Sie auf, was Sie darüber wissen. Sage etwas dazu.
Jetzt sagt nur g x = g x nichts. Natürlich ist es wahr, aber es ist eine sinnlose Tautologie. Wenn wir g x = g (x+2) sagen, ist es keine Tautologie mehr, sondern sinnlos. Wir müssen etwas Sinnvolleres sagen. Zum Beispiel
hier sagten wir etwas . Auch,
%Vor% Haben wir alles gesagt, was wir über x zu sagen hatten? Ob wir es getan haben oder nicht, wir haben es über any x gesagt. Und das schließt unsere rekursive Definition - sobald alle Möglichkeiten ausgeschöpft sind, sind wir fertig .
Aber was ist mit Kündigung ? Wir wollen etwas von unserer Funktion bekommen, wir wollen, dass es seine Arbeit beendet. Das heißt, wenn wir x berechnen, müssen wir sicherstellen, dass wir es rekursiv mit einigen y verwenden, die definiert sind " vor " x , das ist " näher "an einem der einfachsten Fälle, die wir haben .
Und hier haben wir es getan. Jetzt können wir unser Werk bestaunen, mit
%Vor% Das letzte ist, um eine Definition zu verstehen, versuchen Sie nicht, ihre Schritte zurückzuverfolgen. Lesen Sie einfach die Gleichungen selbst. Wenn wir die obige Definition für g erhalten würden, würden wir es einfach wie folgt lesen: g ist eine Boolesche Funktion einer Zahl, die True für 1 und 2 ist, und für jede x > 2 eine Summe seiner zwei vorhergehenden g -Zahlen.
Rekursion ist eine Strategie, um eine gegebene Funktion auf eine gegebene Menge anzuwenden. Sie wenden die Funktion auf das erste Element der Menge an, dann wiederholen Sie den Vorgang für die verbleibenden Elemente der Menge.
Nehmen wir ein Beispiel, Sie möchten die ganze Zahl innerhalb einer Liste verdoppeln. Zuerst denkst du, welche Funktion ich anwenden möchte? Antwort - & gt; 2* , jetzt müssen Sie diese Funktion rekursiv anwenden. Lass es uns apply_rec nennen, also hast du:
Aber das ändert nur das erste Element, Sie wollen alle Elemente auf dem Set ändern. Sie müssen also den apply_rec auf die restlichen Elemente anwenden. Also:
Aber Sie haben jetzt ein Problem. Wann endet apply_rec ? Endet, wenn Sie das Ende der Liste erreichen. In einem anderen Wort [] , also müssen Sie diese neue Prämisse definieren.
Wenn Sie das Ende erreicht haben, möchten Sie keine Funktion mehr anwenden, also haben Sie dieses Verhalten definiert. Wenn also das Ende erreicht ist, sollte die Funktion apply_rec " [] " zurückgeben.
Sehen wir uns das Verhalten dieser Funktion in einem Set an = [1,2,3] .
apply_rec [1,2,3] = (2 * 1) : (apply_rec [2,3]) apply_rec [2,3] = 2 : ((2 * 2) : (apply_rec [3])) apply_rec [3] = 2 : (4 : ((2 * 3) : (apply_rec [])) apply_rec [] = 2 : (4 : (6 : []))) ergibt [2,4,6] .
Wahrscheinlich, da Sie nicht sehr gut Rekursion wissen, ist das beste Ding anzufangen, wenn einfachere Beispiele diese Sie präsentierten. Und lerne es selbst, auch wenn es Stunden dauert.
Sehen Sie sich auch Rekursion lernen an und Haskell Tutorial 3 - Rekursion .
Vielleicht ist die Art und Weise, wie Sie Ihr Problem präsentieren, nicht das Gute, ich meine, das ist nicht durch die Implementierung einer vorhandenen rekursiven Funktion, die Sie verstehen werden, wie Sie es replizieren können. Ich bevorzuge es, Ihnen einen alternativen Weg zu geben, es könnte als ein methodischer Prozess gesehen werden, der Ihnen hilft, das Standardskelett des rekursiven Aufrufs zu schreiben und dann das Nachdenken über sie zu erleichtern.
Bei all deinem Beispiel geht es um liste, dann ist das erste Zeug, wenn du mit der Liste arbeitest, erschöpfend, ich meine, Mustervergleiche zu verwenden.
%Vor%Nun, der Basisfall konnte nicht rekursiv sein, sonst werden Sie mit einer Endlosschleife enden, dann sollte der Basisfall einen Wert zurückgeben, und der beste Weg, diesen Wert zu erfassen, besteht darin, nach der Typannotation Ihrer Funktion zu suchen .
Zum Beispiel:
%Vor%Könnte Sie ermutigen, den Basisfall als Wert vom Typ [a] zu betrachten, als [] für den umgekehrten Fall
%Vor%Könnte Sie dazu ermutigen, den Basisfall als Wert vom Typ a für maximal
zu betrachtenNun zum rekursiven Teil, wie gesagt sollte die Funktion einen Aufruf von sich selbst beinhalten.
%Vor%mit Spaß, um die Verwendung einer anderen Funktion zu bezeichnen, die dafür verantwortlich ist, die Verkettung eines rekursiven Aufrufs zu realisieren. Um Ihrer Intuition zu helfen, können wir sie als Operator präsentieren.
%Vor%Wenn Sie nun (wieder) die Typannotation Ihrer Funktion (oder kurz den Basisfall) betrachten, sollten Sie in der Lage sein, die Art dieses Operators abzuleiten. Für den umgekehrten Fall, wie es eine Liste zurückgeben sollte, ist der Operator sicherlich die Verkettung (++) und so weiter.
Wenn Sie all diese Dinge zusammenfügen, sollte es nicht so schwer sein, mit der gewünschten Implementierung zu enden.
Natürlich, wie bei jedem anderen Algorithmus, müssen Sie immer ein wenig nachdenken und es gibt kein magisches Rezept, Sie müssen nachdenken. Zum Beispiel, wenn Sie das Maximum des Schwanzes der Liste kennen, was ist das Maximum der Liste?
Tags und Links haskell