Beispiele für rekursive Funktionen

Kann jemand empfehlen, Programmier-Beispiele, die veranschaulichen rekursive Funktionen? Es gibt die üblichen alten Pferde wie Fibonacci-Reihe und Türme von Hanoi, aber alles, was neben Ihnen Spaß machen würde.

Kommentar zu dem Problem
Siehe mein Kommentar auf diese Frage: stackoverflow.com/questions/126756/... Kommentarautor: DutGRIFF

InformationsquelleAutor der Frage Codeslayer | 2008-09-24

  1. 107

    Diese Abbildung ist in Englisch, eher als eine tatsächliche Programmiersprache, aber ist nützlich für die Erklärung des Prozesses in eine nicht-technische Art und Weise:

    Ein Kind konnte nicht schlafen, also Ihre Mutter erzählte eine Geschichte über einen kleinen Frosch, 
 wer nicht schlafen konnte, so ist der Frosch Mutter erzählte eine Geschichte über einen kleinen Bären, 
 wer nicht schlafen konnte, so trägt die Mutter erzählte eine Geschichte über ein kleines Wiesel 
 ...wer schlief ein. 
 ...und der kleine Bär schlief; 
 ...und der kleine Frosch schlief; 
...und das Kind schlief ein.

    InformationsquelleAutor der Antwort ConroyP

  2. 27

    Um verstehen Rekursion, muss man zunächst verstehen,Rekursion.

    InformationsquelleAutor der Antwort Ilya Ryzhenkov

  3. 16

    Die Faustregel für Rekursion "Rekursion, wenn und nur wenn für jede iteration Ihre Aufgabe teilt sich in zwei oder mehr ähnliche Aufgaben".

    Also Fibonacci ist kein gutes Beispiel für Rekursion Anwendung, während Hanoi ist ein guter.

    So dass die meisten der guten Beispiele für die Rekursion sind Baum-traversal in verschiedenen verbirgt.

    Zum Beispiel:
    graph-traversal - die Anforderung, dass besuchte Knoten werden nie wieder besucht effektiv macht graph ein Baum (ein Baum ist ein zusammenhš angender graph ohne einfache Zyklen)

    Teile und herrsche-algorithmen (quick sort, merge sort) - Teile, die nach "Teile" bilden die Kinder-Knoten, "erobern" - Systeme bildet die Kanten von Elternknoten zu Kind-Knoten.

    InformationsquelleAutor der Antwort Kaerber

  4. 15

    Wie zum testen ein string ein Palindrom?

    bool isPalindrome(char* s, int len)
{
  if(len < 2)
    return TRUE;
  else
    return s[0] == s[len-1] && isPalindrome(&s[1], len-2);
}

    Natürlich, Sie könnten dies mit einer Schleife effizienter zu gestalten.

    InformationsquelleAutor der Antwort Kip

  5. 13

    Schreiben Sie eine recursive-descent-parser!

    InformationsquelleAutor der Antwort Martin Cote

  6. 10

    Noch ein paar der "üblichen-verdächtigen" sind Quicksort und MergeSort

    InformationsquelleAutor der Antwort agnul

  7. 8

    Aus der Welt der Mathematik, es ist die Ackermann-Funktion:

    Ackermann(m, n)
{
  if(m==0)
    return n+1;
  else if(m>0 && n==0)
    return Ackermann(m-1, 1);
  else if(m>0 && n>0)
    return Ackermann(m-1, Ackermann(m, n-1));
  else
    throw exception; //not defined for negative m or n
}

    Es immer endet, aber es erzeugt sehr große Ergebnisse auch für sehr kleine Eingänge. Ackermann(4, 2), zum Beispiel, gibt 265536 − 3.

    InformationsquelleAutor der Antwort Kip

  8. 6

    Den interpreter design pattern ist ein ganz gutes Beispiel, weil viele Menschen Sie nicht vor Ort die Rekursion. Der Beispiel-code aufgeführt, der Wikipedia-Artikel verdeutlicht auch, wie diese angewendet werden können. Aber einen viel grundlegenderen Ansatz, der noch implementiert das interpreter-Muster ist eine ToString Funktion für verschachtelte Listen:

    class List {
    public List(params object[] items) {
        foreach (object o in items)
            this.Add(o);
    }

    //Most of the implementation omitted …
    public override string ToString() {
        var ret = new StringBuilder();
        ret.Append("( ");
        foreach (object o in this) {
            ret.Append(o);
            ret.Append(" ");
        }
        ret.Append(")");
        return ret.ToString();
    }
}

var lst = new List(1, 2, new List(3, 4), new List(new List(5), 6), 7);
Console.WriteLine(lst);
//yields:
//( 1 2 ( 3 4 ) ( ( 5 ) 6 ) 7 )

    (Ja, ich weiß, es ist nicht leicht zu erkennen das interpreter-Muster in den oben genannten code, wenn Sie erwarten, dass eine Funktion namens Eval ... aber wirklich, das interpreter-Muster sagt uns nicht, was die Funktion namens oder sogar, was es tut und das GoF Buch explizit listet die oben als ein Beispiel, sagte Muster.)

    InformationsquelleAutor der Antwort Konrad Rudolph

  9. 6

    Meiner Meinung nach, Rekursion ist gut zu wissen, aber die meisten Lösungen verwenden Sie Rekursion könnte auch getan werden, mittels iteration, und die iteration ist bei weitem effizienter.

    Das heißt hier ist eine rekursive Art und Weise zu finden, ein Steuerelement in einem verschachtelten Struktur (wie ASP.NET oder Winforms):

    public Control FindControl(Control startControl, string id)
{
      if (startControl.Id == id)
           return startControl

      if (startControl.Children.Count > 0)
      {
           foreach (Control c in startControl.Children)
           {
                return FindControl(c, id);
           }
      }
      return null;
}

    InformationsquelleAutor der Antwort FlySwat

  10. 6

    Hier ist ein pragmatisches Beispiel aus der Welt der Dateisysteme. Dieses Dienstprogramm rekursiv zählt Dateien unter einem angegebenen directory. (Ich weiß nicht warum, aber ich hatte tatsächlich einen Bedarf für so etwas lange her...) 

    public static int countFiles(File f) {
    if (f.isFile()){
        return 1;
    }

    //Count children & recurse into subdirs:
    int count = 0;
    File[] files = f.listFiles();
    for (File fileOrDir : files) {
        count += countFiles(fileOrDir);
    }
    return count;
}

    (Beachten Sie, dass in Java eine File Instanz darstellen kann entweder eine normale Datei oder ein Verzeichnis. Dieses Dienstprogramm schließt Verzeichnisse aus, die zählen.)

    Einer gemeinsamen real-world-Beispiel wäre z.B. FileUtils.deleteDirectory() von der Commons-IO Bibliothek; siehe API-doc & Quelle.

    InformationsquelleAutor der Antwort Jonik

  11. 4

    Einem real-world-Beispiel ist der "bill-of-Material costing" - problem.

    Nehmen wir an, wir haben ein produzierendes Unternehmen, das macht das Endprodukt aus. Jedes Produkt ist beschreibbar durch eine Liste der Teile und die Zeit, die erforderlich ist, montieren Sie diese Teile. Zum Beispiel fertigen wir hand-Bohrmaschinen von einem Fall, motor, Bohrfutter, Schalter, und Kabel, und es dauert nur 5 Minuten.

    Gegeben eine standard-Lohnkosten pro minute, wie viel kostet die Herstellung jedes unserer Produkte?

    Oh, by the way, einige Teile (z.B. Kabel) gekauft werden, damit wir wissen, Ihre Kosten direkt.

    Aber wir tatsächlich produzieren einige der Teile selbst. Wir machen einen motor aus einem Gehäuse, einem stator, ein rotor, eine Welle und Lager, und es dauert 15 Minuten.

    Und wir machen stator und rotor aus Stanzteilen und Draht, ...

    So, der Bestimmung der Kosten des Endprodukts beträgt tatsächlich zu traversieren der Struktur, die repräsentiert alle ganzen-zur-Liste-der-Teile-Beziehungen werden in unseren Prozessen. Das ist schön ausgedrückt mit einem rekursiven Algorithmus. Es kann sicherlich getan werden iterativ so gut, aber die Kern-Idee bekommt, gemischt mit der do-it-yourself-Buchführung, so ist es nicht so klar, was Los ist.

    InformationsquelleAutor der Antwort joel.neely

  12. 2

    Die hairiest Beispiel, das ich kenne, ist Knuth ' s Mann oder Boy Test.
    Sowie Rekursion es nutzt die Algol-features von verschachtelten Funktionsdefinitionen (Verschlüsse), Funktion, Referenzen und Konstanten - /Funktions-Dualismus (call-by-name).

    InformationsquelleAutor der Antwort Hugh Allen

  13. 2

    Wie andere schon gesagt haben, eine Menge von kanonischen Rekursion Beispiele sind Akademische.

    Einige praktische Anwendungen, die ich 've festgestellt, die in der Vergangenheit:

    1 - Navigation in einer Baumstruktur, wie ein Dateisystem oder in der Registrierung

    2 - Manipulation container-Steuerelemente enthalten können andere container-Steuerelemente (wie Platten oder GroupBoxes)

    InformationsquelleAutor der Antwort JosephStyons

  14. 1

    Mein persönlicher Favorit ist Binäre Suche

    Edit: Außerdem, Baum-traversal. Fuß nach unten in einen Ordner-Datei-Struktur zum Beispiel.

    InformationsquelleAutor der Antwort Geoff

  15. 1

    Implementierung Von Graphen , die von Guido van Rossum hat einige rekursive Funktionen in Python zu finden, die Pfade zwischen zwei Knoten im Graphen.

    InformationsquelleAutor der Antwort sanxiyn

  16. 1

    Mein Lieblings-Art, Merge-Sort

    (Favorit seit ich denken kann, ist der Algorithmus und ist es nicht schade performance-wise)

    InformationsquelleAutor der Antwort crashmstr

  17. 0
    • Fakultät
    • Traversierung eines Baumes in die Tiefe (in ein Dateisystem, ein Spiel-Raum, oder in jedem anderen Fall)

    InformationsquelleAutor der Antwort Vinko Vrsalovic

  18. 0

    Wie etwa das umkehren eines Strings?

    void rev(string s) {
  if (!s.empty()) {
    rev(s[1..s.length]);
  }
  print(s[0]);
}

    Verständnis dieses hilft, zu verstehen Rekursion.

    InformationsquelleAutor der Antwort Yuval F

  19. 0

    Hier ist eine Probe, die ich auf dieser Website veröffentlicht eine Weile zurück, für die rekursiv erzeugen Sie ein Menü-Baum: Rekursives Beispiel

    InformationsquelleAutor der Antwort JPrescottSanders

  20. 0

    Wie über alles Verarbeitung von Listen, wie:

    • Karte (und andmap, ormap)
    • fold (foldl, foldr)
    • filter
    • etc...

    InformationsquelleAutor der Antwort pkaeding

  21. 0

    Once upon a time, nicht so lange her, Kinder der Grundschule gelernt Rekursion mit Logo und Turtle-Grafik. http://en.wikipedia.org/wiki/Turtle_graphics

    Rekursion ist auch ideal für das lösen von Rätseln durch erschöpfende Studie. Es ist eine Art von puzzle aufgerufen, ein "fill in" (Google es), in dem Sie bekommen ein Gitter wie ein Kreuzworträtsel, und die Worte, aber keine konkreten Hinweise, keine nummerierten Plätze. Ich schrieb mal ein Programm unter Verwendung von Rekursion für ein puzzle publisher das Rätsel zu lösen, um sicher sein, dass die Lösung bekannt ist, war einzigartig.

    InformationsquelleAutor der Antwort SeaDrive

  22. 0

    Rekursive Funktionen sind ideal für arbeiten mit rekursiv definierte Datentypen:

    • Eine Natürliche Zahl null ist, oder der Nachfolger einer anderen natürlichen Zahl
    • Eine Liste ist die leere Liste oder eine andere Liste mit einem element vor
    • Ein Baum ist ein Knoten mit einigen Daten und null oder mehr Teilbäume

    Etc.

    InformationsquelleAutor der Antwort Bruno De Fraine

  23. -1

    Übersetzen-spreadsheet-Spalte index auf eine Spalte name.

    Es ist schwieriger als es klingt, da spreadsheet-Spalten nicht behandeln, '0' Ziffer richtig. Zum Beispiel, wenn Sie nehmen A-Z als Ziffern, wenn Sie die Inkrement von Z, AA, es wäre wie von 9 auf 11 oder 9, 00 statt um 10 (je nachdem, ob Eine 1 oder 0). Auch die Microsoft-Support-Beispiel bekommt es falsch, für alles, was höher als AAA!

    Die rekursive Lösung funktioniert, da kann man recurse Recht auf diejenigen, die neu-stellige boundries. Diese Implementierung ist in VB.Net und behandelt die erste Spalte ('A') index 1.

    Function ColumnName(ByVal index As Integer) As String
    Static chars() As Char = {"A"c, "B"c, "C"c, "D"c, "E"c, "F"c, "G"c, "H"c, "I"c, "J"c, "K"c, "L"c, "M"c, "N"c, "O"c, "P"c, "Q"c, "R"c, "S"c, "T"c, "U"c, "V"c, "W"c, "X"c, "Y"c, "Z"c}

    index -= 1 'adjust index so it matches 0-indexed array rather than 1-indexed column'

    Dim quotient As Integer = index \ 26 'normal /operator rounds. \ does integer division'
    If quotient > 0 Then
        Return ColumnName(quotient) & chars(index Mod 26)
    Else
        Return chars(index Mod 26)
    End If
End Function

    InformationsquelleAutor der Antwort Joel Coehoorn

Schreibe einen Kommentar