Beispiele für Rekursionen in der Praxis

Ein reales Beispiel für Rekursion

Was ist mit einer Verzeichnisstruktur im Dateisystem? Dateien rekursiv suchen, Dateien löschen, Verzeichnisse erstellen usw.

Hier ist eine Java -Implementierung, die den Inhalt eines Verzeichnisses und seiner Unterverzeichnisse rekursiv ausgibt.

import Java.io.File;

public class DirectoryContentAnalyserOne implements DirectoryContentAnalyser {

    private static StringBuilder indentation = new StringBuilder();

    public static void main (String args [] ){
        // Here you pass the path to the directory to be scanned
        getDirectoryContent("C:\\DirOne\\DirTwo\\AndSoOn");
    }

    private static void getDirectoryContent(String filePath) {

        File currentDirOrFile = new File(filePath);

        if ( !currentDirOrFile.exists() ){
            return;
        }
        else if ( currentDirOrFile.isFile() ){
            System.out.println(indentation + currentDirOrFile.getName());
            return;
        }
        else{
            System.out.println("\n" + indentation + "|_" +currentDirOrFile.getName());
            indentation.append("   ");

            for ( String currentFileOrDirName : currentDirOrFile.list()){
                getPrivateDirectoryContent(currentDirOrFile + "\\" + currentFileOrDirName);
            }

            if (indentation.length() - 3 > 3 ){
                indentation.delete(indentation.length() - 3, indentation.length());
            }
        }       
    }

}

Quicksort , Mergesort und die meisten anderen N-Log-N-Sortierungen.

Das Beispiel von Matt Dillard ist gut. Im Allgemeinen kann jedes Gehen eines Baumes durch Rekursion sehr einfach gehandhabt werden. Zum Beispiel das Kompilieren von Analysebäumen, Übergehen von XML oder HTML usw.

Rekursion wird häufig in Implementierungen des Backtracking-Algorithmus verwendet. Wie wäre es mit einem Sudoku-Löser für eine "reale" Anwendung davon?

Eine Rekursion ist immer dann angebracht, wenn ein Problem durch Unterteilen in Teilprobleme gelöst werden kann, für deren Lösung derselbe Algorithmus verwendet werden kann. Algorithmen für Bäume und sortierte Listen sind eine natürliche Anpassung. Viele Probleme in der Computergeometrie (und in 3D-Spielen) können rekursiv gelöst werden, indem binäre Raumaufteilung (BSP) -Bäume, fette Unterteilungen oder andere Arten der Aufteilung der Welt in Unter- Teile.

Rekursion ist auch dann angebracht, wenn Sie versuchen, die Richtigkeit eines Algorithmus zu gewährleisten. Bei einer Funktion, die unveränderliche Eingaben akzeptiert und ein Ergebnis zurückgibt, das eine Kombination aus rekursiven und nicht rekursiven Aufrufen für die Eingaben darstellt, ist es in der Regel einfach, mithilfe der mathematischen Induktion zu beweisen, dass die Funktion korrekt ist (oder nicht). Es ist oft schwierig, dies mit einer iterativen Funktion oder mit Eingaben zu tun, die möglicherweise mutieren. Dies kann nützlich sein, wenn Sie sich mit Finanzberechnungen und anderen Anwendungen befassen, bei denen Korrektheit sehr wichtig ist.

Sicherlich verwenden viele Compiler eine starke Rekursion. Computersprachen sind von Natur aus rekursiv (d. H. Sie können 'if'-Anweisungen in andere' if'-Anweisungen usw. einbetten).

Deaktivieren/Festlegen des Schreibschutzes für alle untergeordneten Steuerelemente in einem Containersteuerelement. Ich musste das tun, weil einige der Kinder Kontrollen Container selbst waren.

public static void SetReadOnly(Control ctrl, bool readOnly)
{
    //set the control read only
    SetControlReadOnly(ctrl, readOnly);

    if (ctrl.Controls != null && ctrl.Controls.Count > 0)
    {
        //recursively loop through all child controls
        foreach (Control c in ctrl.Controls)
            SetReadOnly(c, readOnly);
    }
}

Famous Eval/Apply-Zyklus von SICP

_{(Quelle: mit.ed )}

Hier ist die Definition von eval:

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp)
                         (lambda-body exp)
                         env))
        ((begin? exp) 
         (eval-sequence (begin-actions exp) env))
        ((cond? exp) (eval (cond->if exp) env))
        ((application? exp)
         (apply (eval (operator exp) env)
                (list-of-values (operands exp) env)))
        (else
         (error "Unknown expression type - EVAL" exp))))

Hier ist die Definition von zutreffen:

(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence
           (procedure-body procedure)
           (extend-environment
             (procedure-parameters procedure)
             arguments
             (procedure-environment procedure))))
        (else
         (error
          "Unknown procedure type - APPLY" procedure))))

Hier ist die Definition von eval-sequence:

(define (eval-sequence exps env)
  (cond ((last-exp? exps) (eval (first-exp exps) env))
        (else (eval (first-exp exps) env)
              (eval-sequence (rest-exps exps) env))))

eval -> apply -> eval-sequence -> eval

Rekursion wird in Dingen wie BSP-Bäumen zur Kollisionserkennung in der Spieleentwicklung (und anderen ähnlichen Bereichen) verwendet.

Menschen sortieren oft Stapel von Dokumenten mit einer rekursiven Methode. Stellen Sie sich zum Beispiel vor, Sie sortieren 100 Dokumente mit Namen. Legen Sie zuerst die Dokumente nach dem ersten Buchstaben in Stapel und sortieren Sie dann jeden Stapel.

Das Nachschlagen von Wörtern im Wörterbuch erfolgt häufig nach einer binären Suchmethode, die rekursiv ist.

In Organisationen erteilen Chefs oft Befehle an Abteilungsleiter, die wiederum Befehle an Manager erteilen, und so weiter.

Rekursion wird auf Probleme (Situationen) angewendet, in denen Sie es in kleinere Teile aufteilen (reduzieren) können und jedes Teil (jede Teile) dem ursprünglichen Problem ähnelt.

Gute Beispiele dafür, wo Dinge, die kleinere Teile enthalten, die sich selbst ähneln, sind:

• baumstruktur (ein Ast ist wie ein Baum)
• listen (Teil einer Liste ist immer noch eine Liste)
• behälter (russische Puppen)
• sequenzen (ein Teil einer Sequenz sieht aus wie die nächste)
• gruppen von Objekten (eine Untergruppe ist immer noch eine Gruppe von Objekten)

Rekursion ist eine Technik, mit der das Problem in immer kleinere Teile zerlegt wird, bis eines dieser Teile klein genug ist, um ein Kinderspiel zu sein. Natürlich müssen Sie die Ergebnisse nach dem Aufteilen wieder in der richtigen Reihenfolge "zusammenfügen", um eine vollständige Lösung für Ihr ursprüngliches Problem zu erhalten.

Einige rekursive Sortieralgorithmen, Tree-Walking-Algorithmen, Map/Reduction-Algorithmen und Divide-and-Conquer sind Beispiele für diese Technik.

Bei der Computerprogrammierung verfügen die meisten stapelbasierten Rückruftypsprachen bereits über die für die Rekursion eingebauten Funktionen: d.h.

• das Problem in kleinere Teile zerlegen ==> sich auf eine kleinere Teilmenge der ursprünglichen Daten beziehen),
• verfolgen Sie, wie die Teile aufgeteilt sind ==> Aufrufstapel,
• nähen Sie die Ergebnisse zurück ==> stapelbasierte Rückgabe

Einige großartige Beispiele für Rekursionen sind in funktionale Programmierung Sprachen zu finden. In funktionalen Programmiersprachen ( Erlang , Haskell , ML / OCaml / F # , etc.), es ist sehr üblich, dass eine Listenverarbeitung eine Rekursion verwendet.

Beim Umgang mit Listen in typischen imperativen OOP-Sprachen werden Listen häufig als verknüpfte Listen implementiert ([item1 -> item2 -> item3 -> item4]). In einigen funktionalen Programmiersprachen stellen Sie jedoch fest, dass Listen selbst rekursiv implementiert werden, wobei der "Kopf" der Liste auf das erste Element in der Liste und der "Schwanz" auf eine Liste mit den übrigen Elementen verweist ( [item1 -> [item2 -> [item3 -> [item4 -> []]]]]). Es ist meiner Meinung nach ziemlich kreativ.

Dieser Umgang mit Listen ist in Kombination mit Pattern Matching SEHR leistungsfähig. Angenommen, ich möchte eine Liste von Zahlen zusammenfassen:

let rec Sum numbers =
    match numbers with
    | [] -> 0
    | head::tail -> head + Sum tail

Dies besagt im Wesentlichen "Wenn wir mit einer leeren Liste aufgerufen wurden, geben Sie 0 zurück" (was uns erlaubt, die Rekursion zu unterbrechen), andernfalls geben Sie den Wert von head + den Wert von Sum zurück, der mit den verbleibenden Elementen aufgerufen wurde (daher unsere Rekursion).

Zum Beispiel könnte ich eine Liste von RLs haben. Ich denke, ich zerlege alle URLs, auf die jede URL verweist, und dann reduziere ich die Gesamtzahl der Links zu/von allen URLs, um "Werte" zu generieren eine Seite (ein Ansatz, den Google mit PageRank verfolgt und den Sie im Originalpapier MapReduce finden). Auf diese Weise können Sie auch Word-Zählungen in einem Dokument generieren. Und viele, viele, viele andere Dinge.

Sie können dieses Funktionsmuster auf jede Art von MapReduce Code erweitern, mit dem Sie eine Liste von etwas erstellen, transformieren und etwas anderes zurückgeben können (egal ob eine andere Liste oder ein Zip-Befehl in der Liste).

Anforderungen aus der realen Welt, die ich kürzlich erhalten habe:

Anforderung A: Implementieren Sie diese Funktion, nachdem Sie die Anforderung A vollständig verstanden haben.

Parser und Compiler können in einer rekursiven Abstiegsmethode geschrieben werden. Dies ist nicht der beste Weg, da Tools wie Lex/yacc schnellere und effizientere Parser generieren, aber konzeptionell einfach und leicht zu implementieren sind, sodass sie weiterhin üblich sind.

Ich habe ein System, das an einigen Stellen pure Schwanzrekursion verwendet, um eine Zustandsmaschine zu simulieren.

XML oder über alles, was ein Baum ist. Obwohl ich, um ehrlich zu sein, in meinem Job so gut wie nie Rekursion benutze.

Feedbackschleifen in einer hierarchischen Organisation.

Der Top-Chef fordert die Top-Führungskräfte auf, Feedback von allen Mitarbeitern des Unternehmens einzuholen.

Jede Führungskraft sammelt ihre direkten Berichte und fordert sie auf, Feedback zu ihren direkten Berichten einzuholen.

Und auf der ganzen Linie.

Personen ohne direkten Bericht - die Blattknoten im Baum - geben ihr Feedback.

Das Feedback wandert den Baum hinauf, wobei jeder Manager sein eigenes Feedback hinzufügt.

All das Feedback macht es schließlich wieder zum Top-Boss.

Dies ist die natürliche Lösung, da die rekursive Methode das Filtern auf jeder Ebene ermöglicht - das Zusammentragen von Duplikaten und das Entfernen von anstößigem Feedback. Der Top-Chef könnte eine globale E-Mail senden und jedem Mitarbeiter Feedback direkt zukommen lassen, aber es gibt die Probleme "Sie können nicht mit der Wahrheit umgehen" und "Sie sind gefeuert" Also funktioniert Rekursion hier am besten.

Berechnungen für Finanzen/Physik, z. B. Durchschnittswerte.

Das beste Beispiel, das ich kenne, ist quicksort , es ist viel einfacher mit Rekursion. Schauen Sie sich an:

shop.oreilly.com/product/9780596510046.do

www.Amazon.com/Beautiful-Code-Leading-Programmers-Practice/dp/0596510047

(Klicken Sie auf den ersten Untertitel unter Kapitel 3: "Der schönste Code, den ich je geschrieben habe").

• Analysieren einer XML -Datei.
• Effiziente Suche in mehrdimensionalen Räumen. Z.B. Quad-Bäume in 2D, Oct-Bäume in 3D, KD-Bäume usw.
• Hierarchisches Clustering.
• Denken Sie darüber nach, wenn Sie eine hierarchische Struktur durchqueren, kann dies natürlich zu einer Rekursion führen.
• Template-Metaprogrammierung in C++, wo es keine Schleifen und Rekursionen gibt, ist der einzige Weg.

Angenommen, Sie erstellen ein CMS für eine Website, auf der sich Ihre Seiten in einer Baumstruktur befinden, wobei das Stammverzeichnis beispielsweise die Homepage ist.

Angenommen, auch Ihr {user | client | customer | boss} fordert Sie auf, auf jeder Seite einen Breadcrumb-Trail zu platzieren, um anzuzeigen, wo Sie sich im Baum befinden.

Für eine bestimmte Seite n möchten Sie möglicherweise rekursiv zum übergeordneten Element von n und seinem übergeordneten Element usw. gehen, um eine Liste von Knoten zu erstellen, die bis zum Stamm des Seitenbaums zurückgeführt werden.

Natürlich treffen Sie in diesem Beispiel die Datenbank mehrmals pro Seite, daher möchten Sie möglicherweise ein SQL-Aliasing verwenden, bei dem Sie die Seitentabelle als a und die Seitentabelle erneut als b nachschlagen und a.id mit verknüpfen Übergeordnet, damit die Datenbank die rekursiven Verknüpfungen ausführt. Es ist schon eine Weile her, daher ist meine Syntax wahrscheinlich nicht hilfreich.

Andererseits möchten Sie diesen Wert möglicherweise nur einmal berechnen und zusammen mit dem Seitendatensatz speichern. Er wird nur aktualisiert, wenn Sie die Seite verschieben. Das wäre wahrscheinlich effizienter.

Wie auch immer, das sind meine $ .02

Sie haben einen Organisationsbaum mit einer Tiefe von N Ebenen. Einige der Knoten sind markiert, und Sie möchten nur die Knoten markieren, die markiert wurden.

Dies ist etwas, das ich tatsächlich codiert habe. Es ist schön und einfach mit Rekursion.

Analysieren eines Steuerelementbaums in Windows Forms oder WebForms (.NET Windows Forms/ ASP.NET ).

In meinem Job haben wir ein System mit einer generischen Datenstruktur, die als Baum beschrieben werden kann. Das bedeutet, dass die Rekursion eine sehr effektive Technik ist, um mit den Daten zu arbeiten.

Das Lösen ohne Rekursion würde eine Menge unnötigen Codes erfordern. Das Problem bei der Rekursion ist, dass es nicht einfach ist zu verfolgen, was passiert. Sie müssen sich wirklich konzentrieren, wenn Sie dem Ablauf der Ausführung folgen. Aber wenn es funktioniert, ist der Code elegant und effektiv.

Alles, wo Sie Iteration verwenden, geschieht natürlicher mit Rekursion, wenn es nicht die praktische Einschränkung gibt, einen Stapelüberlauf zu verursachen ;-)

Aber ernsthaft Rekursion und Iteration sind sehr austauschbar. Sie können alle Algorithmen mit Rekursion neu schreiben, um Iteration zu verwenden, und umgekehrt. Mathematiker mögen Rekursion und Programmierer mögen Iteration. Das ist wahrscheinlich auch der Grund, warum Sie all diese erfundenen Beispiele sehen, die Sie erwähnen. Ich denke, dass die Methode des mathematischen Beweises, die als mathematische Induktion bezeichnet wird, etwas zu tun hat, warum Mathematiker Rekursion mögen. http://en.wikipedia.org/wiki/Mathematical_induction

Die Multiplikation natürlicher Zahlen ist ein reales Beispiel für die Rekursion:

To multiply x by y
  if x is 0
    the answer is 0
  if x is 1
    the answer is y
  otherwise
    multiply x - 1 by y, and add x

Methoden zum Finden von Primzahlen sind rekursiv. Nützlich zum Generieren von Hash-Schlüsseln für verschiedene Verschlüsselungsschemata, die Faktoren mit großen Zahlen verwenden.

Telefon- und Kabelunternehmen pflegen ein Modell ihrer Verkabelungstopologie, bei der es sich im Grunde um ein großes Netzwerk oder einen Graphen handelt. Rekursion ist eine Möglichkeit, dieses Modell zu durchlaufen, wenn Sie alle übergeordneten oder alle untergeordneten Elemente suchen möchten.

Da die Rekursion unter Verarbeitungs- und Speichergesichtspunkten teuer ist, wird dieser Schritt normalerweise nur ausgeführt, wenn die Topologie geändert und das Ergebnis in einem geänderten vorbestellten Listenformat gespeichert wird.

Induktives Denken, der Prozess der Begriffsbildung, ist von Natur aus rekursiv. Ihr Gehirn macht es die ganze Zeit in der realen Welt.

Meistens ist die Rekursion für den Umgang mit rekursiven Datenstrukturen sehr natürlich. Dies bedeutet im Grunde Listenstrukturen und Baumstrukturen. Aber Rekursion ist auch eine nette natürliche Methode, um Baumstrukturen im laufenden Betrieb zu erstellen, zum Beispiel durch Teilen und Erobern Quicksort oder binäre Suche.

Ich denke, Ihre Frage ist in gewisser Hinsicht ein bisschen fehlgeleitet. Was ist nicht realistisch an der Tiefensuche? Mit der Tiefensuche können Sie viel anfangen.

Ein anderes Beispiel, an das ich gedacht habe, ist die rekursive Abstiegskompilierung. Es ist genug von einem realen Problem, in vielen realen Compilern verwendet worden zu sein. Man könnte jedoch behaupten, dass es sich um DFS handelt. Es handelt sich im Grunde genommen um eine Tiefensuche nach einem gültigen Analysebaum.

Ich habe einmal einen XML-Parser geschrieben, der ohne Rekursion viel schwieriger zu schreiben gewesen wäre.

Ich nehme an, Sie können immer einen Stapel + Iteration verwenden, aber manchmal ist die Rekursion einfach so elegant.

Jedes Programm mit Baum- oder Graphendatenstrukturen wird wahrscheinlich eine Rekursion haben.

Ermittlung des Medians im Durchschnittsfall O (n). Entspricht dem Finden des k-größten Elements in einer Liste von n Dingen mit k = n/2:

Hier wählt partition ein Pivot-Element aus und ordnet die Liste in einem Durchgang durch die Daten neu an, sodass zuerst Elemente, die kleiner als der Pivot sind, dann der Pivot und dann Elemente, die größer als der Pivot sind. Der "kthLargest" -Algorithmus ist dem Quicksort sehr ähnlich, findet sich jedoch nur auf einer Seite der Liste wieder.

Für mich ist dies der einfachste rekursive Algorithmus, der schneller ausgeführt wird als ein iterativer Algorithmus. Es werden im Durchschnitt 2 * n Vergleiche verwendet, unabhängig von k. Dies ist viel besser als der naive Ansatz, k durch die Daten zu laufen, das Minimum jedes Mal zu finden und es zu verwerfen.

Alejo

Ebenso der Kommentar zu Compilern. Die abstrakten Syntaxbaumknoten eignen sich natürlich zur Rekursion. Alle rekursiven Datenstrukturen (verknüpfte Listen, Bäume, Diagramme usw.) lassen sich auch mit der Rekursion einfacher handhaben. Ich glaube, dass die meisten von uns nach der Schulzeit wegen der Art der realen Probleme nicht viel mit Rekursion zu tun haben, aber es ist gut, sich dessen bewusst zu sein.

Schreiben Sie eine Funktion, die eine Zahl wie 12345,67 in "zwölftausenddreihundertfünfundvierzig Dollar und siebenundsechzig Cent" umsetzt.

1. Der College-Sparplan: Lassen Sie A(n) = nach n Monaten für das College gesparter Betrag A(0) = $ 500 Jeden Monat werden $ 50 auf einen eingezahlt Konto, das 5% an jährlichen Zinsen verdient.

Dann A(n) = A(n-1) + 50 + 0.05*(1/12)* A(N-1)

Ich habe einen Baum in C # geschrieben, um Suchvorgänge für eine Tabelle durchzuführen, die einen 6-segmentierten Schlüssel mit Standardfällen enthält (wenn der Schlüssel [0] nicht vorhanden ist, verwenden Sie den Standardfall und fahren Sie fort). Die Suchen wurden rekursiv durchgeführt. Ich habe ein Wörterbuch mit Wörterbüchern (usw.) ausprobiert und es wurde sehr schnell viel zu komplex.

Ich habe auch einen Formelauswerter in C # geschrieben, der in einem Baum gespeicherte Gleichungen auswertet, um die richtige Auswertungsreihenfolge zu erhalten. Zugegeben, dies ist wahrscheinlich ein Fall, in dem die falsche Sprache für das Problem ausgewählt wurde, aber es war eine interessante Übung.

Ich sah nicht viele Beispiele dafür, was die Leute getan hatten, sondern Bibliotheken, die sie benutzt hatten. Hoffentlich gibt Ihnen dies etwas zu denken.

Eine Methode zum Generieren eines baumstrukturierten Menüs aus einer Datenbanktabelle unter Verwendung von Unterschall.

public MenuElement(BHSSiteMap node, string role)
    {
        if (CheckRole(node, role))
        {
            ParentNode = node;

            // get site map collection order by sequence
            BHSSiteMapCollection children = new BHSSiteMapCollection();

            Query q = BHSSiteMap.CreateQuery()
                    .WHERE(BHSSiteMap.Columns.Parent, Comparison.Equals, ParentNode.Id)
                    .ORDER_BY(BHSSiteMap.Columns.Sequence, "ASC");

            children.LoadAndCloseReader(q.ExecuteReader());

            if (children.Count > 0)
            {
                ChildNodes = new List<MenuElement>();

                foreach (BHSSiteMap child in children)
                {
                    MenuElement childME = new MenuElement(child, role);
                    ChildNodes.Add(childME);
                }
            }
        }
    }

Geometrische Berechnungen für GIS oder Kartografie, z. B. das Ermitteln der Kante eines Kreises.

Methoden zum Finden einer Quadratwurzel sind rekursiv. Nützlich für die Berechnung von Entfernungen in der realen Welt.

Das letzte reale Beispiel, das ich habe, ist ziemlich frivol, aber es zeigt, wie Rekursion manchmal einfach passt.

Ich habe das Muster "Chain of Responsibility" verwendet, sodass ein Handler-Objekt eine Anforderung entweder selbst verarbeitet oder sie entlang der Kette delegiert. Es ist nützlich, den Aufbau der Kette zu protokollieren:

public String getChainString() {
    cs = this.getClass().toString();
    if(this.delegate != null) {
        cs += "->" + delegate.getChainString();
    }
    return cs;
}

Man könnte argumentieren, dass dies nicht die reinste Rekursion ist, denn obwohl die Methode "sich selbst" aufruft, befindet sie sich bei jedem Aufruf in einer anderen Instanz.

Du hast ein Gebäude. Das Gebäude verfügt über 20 Zimmer. Rechtlich gesehen können Sie nur eine bestimmte Anzahl von Personen in jedem Raum haben. Ihre Aufgabe ist es, einem Raum automatisch Personen zuzuweisen. Sollte mein Zimmer voll sein, müssen Sie ein freies Zimmer finden. Da nur bestimmte Räume bestimmte Personen aufnehmen können, müssen Sie auch darauf achten, in welchem ​​Raum Sie sich befinden.

Beispielsweise:

Die Räume 1, 2, 3 können ineinander rollen. Dieses Zimmer ist für Kinder gedacht, die nicht alleine gehen können. Sie möchten, dass sie nicht abgelenkt werden, um Ablenkungen und andere Krankheiten zu vermeiden (was für ältere Menschen nichts ist, für 6 Monate jedoch sehr schlimm werden kann. Sollte Sind alle drei voll, muss der Person der Zutritt verweigert werden.

Die Räume 4, 5, 6 können sich gegenseitig einrollen. Dieses Zimmer ist für Personen gedacht, die allergisch gegen Erdnüsse sind und daher nicht in andere Zimmer gehen können (die möglicherweise Sachen mit Erdnüssen enthalten). Sollten alle drei voll sein, bieten Sie eine Warnung an, in der Sie nach dem Allergiestatus und der möglichen Zugangsberechtigung gefragt werden.

Die Zimmer können sich jederzeit ändern. Sie können also Zimmer 7-14 als No-Peanut-Zimmer zulassen. Sie wissen nicht, wie viele Zimmer überprüft werden müssen.

Oder möchten Sie sich nach Alter trennen? Note, Geschlecht usw. Dies sind nur einige Beispiele, auf die ich eingegangen bin.

Stecker: http://picogen.deviantart.com/gallery/

Ein "reales" Problem, das durch Rekursion gelöst wird, ist das Verschachteln von Puppen. Deine Funktion ist OpenDoll ().

Mit einem Stapel davon würden Sie die Puppen rekursiv öffnen und OpenDoll () aufrufen, bis Sie die innerste Puppe erreicht haben.

Wenn Sie zwei unterschiedliche, aber ähnliche Sequenzen haben und die Komponenten jeder Sequenz so zuordnen möchten, dass große zusammenhängende Abschnitte bevorzugt werden, gefolgt von identischer Sequenzreihenfolge, können Sie diese Sequenzen rekursiv analysieren, um einen Baum zu bilden, und diesen Baum dann rekursiv verarbeiten, um sie zu reduzieren es.

Referenz: Rekursions- und Memo-Beispielcode

Ich habe gerade eine rekursive Funktion geschrieben, um herauszufinden, ob eine Klasse mithilfe eines DataContractSerializers serialisiert werden musste. Das große Problem waren Vorlagen/Generika, bei denen eine Klasse andere Typen enthalten konnte, die für die Serialisierung von Datenkontrakten erforderlich waren. Wenn es sich also nicht um datenkontraktierbare Typen handelt, überprüfen Sie ihre Typen.

Wir verwenden sie, um SQL-Pfade zu finden.

Ich werde auch sagen, dass das Debuggen mühsam ist und es für einen armen Programmierer sehr einfach ist, es zu vermasseln.

Rekursion ist eine sehr grundlegende Programmiertechnik, und es bietet sich für so viele Probleme an, dass das Auflisten mit dem Auflisten aller Probleme vergleichbar ist, die durch die Verwendung einer Art von Addition gelöst werden können. Ich gehe meine LISP-Lösungen für Project Euler durch und finde: eine Quersummenfunktion, eine Ziffernanpassungsfunktion, mehrere Funktionen zum Durchsuchen eines Leerzeichens, einen minimalen Textparser, eine Funktion, die eine Zahl in die Liste ihrer Dezimalstellen aufteilt, eine Funktion Erstellen eines Graphen und einer Funktion, die eine Eingabedatei durchläuft.

Das Problem ist, dass viele, wenn nicht die meisten gängigen Programmiersprachen heutzutage keine Tail-Call-Optimierung haben, so dass eine tiefe Rekursion mit ihnen nicht möglich ist. Diese Unzulänglichkeit bedeutet, dass die meisten Programmierer gezwungen sind, diese natürliche Denkweise zu verlernen und sich stattdessen auf andere, wohl weniger elegante Loop-Konstrukte zu verlassen.

Da Sie anscheinend keine Informatik- oder Mathematikbeispiele mögen, ist dies ein anderes: Drahtpuzzles.

Bei vielen Drahtpuzzles wird eine lange, geschlossene Drahtschleife entfernt, indem sie in Drahtringe eingearbeitet und aus diesen herausgenommen wird. Diese Rätsel sind rekursiv. Eine davon heißt "Pfeildynamik". Ich bin sicher, Sie könnten es finden, wenn Sie für "Pfeil Dynamik Draht Puzzle" google

Diese Rätsel sind den Türmen von Hanoi sehr ähnlich.

Überprüfen Sie, ob das erstellte Bild in einem Feld mit Größenbeschränkung funktioniert.

function check_size($font_size, $font, $text, $width, $height) {
        if (!is_string($text)) {
            throw new Exception('Invalid type for $text');
        }   
        $box = imagettfbbox($font_size, 0, $font, $text);
        $box['width'] = abs($box[2] - $box[0]);
        if ($box[0] < -1) {
            $box['width'] = abs($box[2]) + abs($box[0]) - 1;
        }   
        $box['height'] = abs($box[7]) - abs($box[1]);
        if ($box[3] > 0) {
            $box['height'] = abs($box[7] - abs($box[1])) - 1;
        }   
        return ($box['height'] < $height && $box['width'] < $width) ? array($font_size, $box['width'], $height) : $this->check_size($font_size - 1, $font, $text, $width, $height);
    }

Ich denke, das hängt wirklich von der Sprache ab. In einigen Sprachen, z. B. LISP , ist die Rekursion häufig die natürliche Reaktion auf ein Problem (und in Sprachen, in denen dies der Fall ist, wird der Compiler optimiert befassen sich mit Rekursion).

Das in LISP übliche Muster, eine Operation für das erste Element einer Liste auszuführen und dann die Funktion für den Rest der Liste aufzurufen, um entweder einen Wert oder eine neue Liste zu akkumulieren, ist recht elegant und die natürlichste Methode, um viel zu tun Dinge in dieser Sprache. In Java nicht so sehr.