Rekursive Programmierung beherrschen

Mein Ratschlag: Vertrauen, dass die rekursive Funktion "macht den job", d.h. es erfüllt die Spezifikation. Und zu wissen, dass, können Sie bauen eine Funktion, löst ein größeres problem, während immer noch die Erfüllung der Spezifikation.

Wie lösen Sie die Türme von Hanoi-problem ? Angenommen, es gibt eine Funktion Hanoi(N) zu verschieben, können Sie einen Stapel von N Scheiben ohne Verstoß gegen die Regeln. Mit dieser Funktion, die Sie leicht umsetzen Hanoi'(N+1): führen Hanoi(N), bewegen Sie den nächsten Datenträger, und führen Hanoi(N) wieder.

Wenn Hanoi(N) arbeitet, dann Hanoi'(N+1) funktioniert so gut, ohne Verstoß gegen die Regeln. Zum Abschluss der argument, müssen Sie sicherstellen, dass die rekursiven Aufrufe werden beendet. In diesem Fall, wenn Sie lösen können, die von Hanoi(1) nicht rekursiv (das ist trivial), sind Sie fertig.

Dieser Ansatz, Sie haben keine sorgen zu machen darüber, wie die Dinge tatsächlich auftreten, Sie werden garantiert, dass es funktioniert. (Vorausgesetzt, Sie bewegen sich, um kleinere und kleinere Instanzen des Problems.)

Anderes Beispiel: rekursive Traversierung eines binären Baum. Übernehmen die Funktion Visit(root) macht den job. Dann if left -> Visit(left); if right -> Visit(right); print root wird die Arbeit machen ! Da der erste Aufruf wird gedruckt, der linke Teilbaum (nicht sich sorgen, wie Sie) und die zweite den rechten Teilbaum (keine Sorge, wie), und das root-gedruckt werden zu können.

Im letzteren Fall ist die Kündigung durch die Tatsache gewährleistet, dass Sie Prozess kleiner und kleiner Teilbäume, nach unten zu Blättern.

Anderes Beispiel: Quicksort. Angenommen, Sie haben eine Funktion sortiert ein array in-place, lassen Sie Quicksort. Verwenden Sie es wie folgt: bewegen sich die kleinen Elemente, bevor Sie große Elemente, in-place, im Vergleich zu einem gut gewählten "pivot" - Wert (eigentlich jeden Wert aus dem array). Dann Sortieren Sie die kleinen Elemente mit Hilfe des Quicksort-Funktion, und die großen Elemente die gleiche Weise, und Sie sind fertig ! Keine Notwendigkeit zu Fragen, die genaue Reihenfolge der Partitionen, die stattfinden werden. Die Kündigung ist gewährleistet, wenn Sie vermeiden void subarrays.

Letztes Beispiel, Pascal ' s Triangle. Sie wissen, dass ein element ist die Summe der beiden über ihm, mit 1 Seiten. So mit geschlossenen Augen, C(K, N)= 1 if K=0 or K=N, else C(K, N) = C(K-1, N-1) + C(K, N-1). Das ist es !

InformationsquelleAutor der Antwort Yves Daoust

Rekursion ist ein bequemer Weg zur Umsetzung des Divide & Conquer-Paradigma: wenn Sie Sie brauchen, die zur Lösung eines bestimmten Problems, einer leistungsstarken Lösung ist, es zu brechen in Probleme von der gleichen Art, aber mit einer kleineren Größe. Durch die Wiederholung dieses Prozesses, werden Sie am Ende der Arbeit auf Probleme so klein sind, dass Sie können leicht gelöst werden durch eine andere Methode.

Die Frage, die Sie haben, um sich Fragen, "kann ich lösen dieses problem durch die Lösung teilen ?". Wenn die Antwort positiv ist, wenden Sie das bekannte Schema:

• aufteilen des Problems in Teilprobleme rekursiv, bis die Größe ist klein,

• lösen Sie die Teilprobleme, die durch eine direkte Methode,

• Zusammenführen der Lösungen in der umgekehrten Reihenfolge.

Hinweis, dass die Spaltung kann in zwei Teile oder mehr, und können diese ausgeglichen werden oder nicht.

Zum Beispiel: kann ich ein array Sortieren von zahlen, die von der Durchführung teilweise sortiert ?

Antwort 1: ja, wenn ich das Letzte element aus und Sortieren den rest, ich kann irgendwie die ganze Palette durch einfügen, die das Letzte element an der richtigen Stelle. Dies ist insertion sort.

Antwort 2: ja, wenn ich finde das größte element und verschieben Sie es bis zum Ende, ich kann irgendwie die ganze Palette durch Sortieren der verbleibenden Elemente. Dies ist die Auswahl Sortieren.

Antwort 3: ja, wenn ich irgendwie zwei Hälften des Arrays, ich kann irgendwie die ganze Palette durch Zusammenlegung der beiden Sequenzen, die mit einem Hilfs-array für die Bewegungen. Dies ist merge-sort.

Antwort 4: ja, wenn ich die partition dem array mit einer pivot, ich kann irgendwie die ganze Palette durch Sortieren der beiden Teile. Dies ist quick sort.

In all diesen Fällen, die Sie lösen das problem durch Lösung der Teilprobleme der gleichen Art und das hinzufügen von etwas Kleber.

InformationsquelleAutor der Antwort Yves Daoust

Für komplexe Probleme zu lösen, empfehle ich tun, das problem für kleine Größen problem und sehen, welche Arten von Muster, die Sie finden. Zum Beispiel, in den Türmen von Hanoi starten Sie mit einer problem-Größe von eins, dann zwei, dann drei, usw. An einem gewissen Punkt, werden Sie wahrscheinlich beginnen, um zu sehen, ein Muster, und Sie werden erkennen, dass einiges von dem, was Sie tun, ist genau das, was Sie zu tun hatten, auf die kleineren Probleme, oder, dass es ähnlich genug, dass Sie können verwenden die gleiche Technik wie zuvor, jedoch mit einigen Variationen.

Ging ich einfach durch die Türme von Hanoi problem mich und studierte mein eigenes denken. Ich begann mit einem problem der Größe:

 Wir haben eine Festplatte auf peg-A. 
 *** Verschieben der peg-C. 
 Fertig! 

Nun für zwei.

 Wir habe zwei Festplatten auf peg-A. 
 Ich brauche zur Verwendung von peg-B, um die erste Platte aus dem Weg. 
 *** Verschieben von Stange A nach Stange B 
 Jetzt kann ich den rest erledigen 
 *** Verschieben von Stange A nach Stange C 
 *** Verschieben von Stange B nach Stange C 
 Fertig! 

Nun für drei.

Beginnen die Dinge ein wenig interessanter. Die Lösung ist nicht so offensichtlich. Allerdings habe ich herausgefunden, wie bewegen Sie zwei Scheiben von einer Stange zur anderen, so dass, wenn ich könnte schieben Sie zwei Scheiben von Stange A nach Stange B, dann bewegen sich eine Scheibe von Stange A nach Stange C, und dann zwei Scheiben von Stange B nach Stange C, hätte ich es getan!
Meine Logik für den Fall von zwei Festplatten die Arbeit, außer dass die Heringe sind unterschiedlich. Wenn wir die Logik in eine Funktion, und stellen Sie die Parameter für die Heringe, dann können wir wieder die Logik.

def move2(from_peg,to_peg,other_peg):
   # We have two disks on from_peg
   # We need to use other_peg to get the first disk out of the way
   print 'Move from peg '+from_peg+' to peg '+other_peg
   # Now I can do the rest
   print 'Move from peg '+from_peg+' to peg '+to_peg
   print 'Move from peg '+other_peg+' to peg '+to_peg

Die Logik ist dann:

 move2('A','B','C') 
 print 'die Bewegung von Stange A nach Stange C' 
 move2('B','C','A') 

Ich kann machen dies einfacher durch eine Funktion move1 auch:

def move1(from_peg,to_peg):
    print 'Move from '+from_peg+' to '+to_peg

Nun meine move2-Funktion können Sie

def move2(from_peg,to_peg,other_peg):
   # We have two disks on from_peg
   # We need to use other_peg to get the first disk out of the way
   move1(from_peg,other_peg,to_peg)
   # Now I can do the rest
   move1(from_peg,to_peg)
   move1(other_peg,to_peg)

Ok, was ist mit vier?

Scheint, wie ich kann, anwenden der gleichen Logik. Ich brauche, um drei Scheiben von Stange A nach Stange B, dann von A nach C, dann drei von B nach C. ich gelöst, bewegt die drei schon, aber mit der falschen Wirbel, so werde ich verallgemeinern:

def move3(from_peg,to_peg,other_peg):
   move2(from_peg,other_peg,to_peg)
   move1(from_peg,to_peg)
   move2(other_peg,to_peg,from_peg)

Cool! Und warten, move3 und move2 sind ziemlich ähnlich wie jetzt, und das macht Sinn. Für jede Größe problem, das wir bewegen können, alle, aber einer der Festplatten zu peg B, dann bewegen sich eine Scheibe von A nach C, dann bewegen sich alle Datenträger auf peg-B-peg C. Also unsere Funktion verschieben können, nehmen Sie einfach die Anzahl der Festplatten, die als parameter:

def move(n,from_peg,to_peg,other_peg):
    move(n-1,from_peg,other_peg,to_peg)
    move1(from_peg,to_peg)
    move(n-1,other_peg,to_peg,from_peg)

Das sieht wirklich eng, aber es funktioniert nicht in dem Fall, wo n==1, weil wir uns am Ende den Aufruf move(0,...). Also müssen wir, damit umzugehen:

def move(n,from_peg,to_peg,other_peg):
    if n==1:
        move1(from_peg,to_peg)
    else:
        move(n-1,from_peg,other_peg,to_peg)
        move1(from_peg,to_peg)
        move(n-1,other_peg,to_peg,from_peg)

Ausgezeichnet! Was zu einem problem der Größe von fünf? Wir rufen move(5,'A','C','B'). Sieht aus wie jedes problem die Größe ist die gleiche Sache, also unsere main-Funktion ist einfach:

def towers(n):
    move(n,'A','C','B')

, und wir sind fertig!

InformationsquelleAutor der Antwort Vaughn Cato