Praxisbeispiele von Rekursion [geschlossen]

Question

Was sind reale Probleme, bei denen ein rekursive Ansatz ist die natürliche Lösung neben Tiefensuche (DFS)?

(Ich glaube nicht, Tower of Hanoi , Fibonacci-Zahl oder Fakultäts Problemen der realen Welt. Sie sind ein wenig gekünstelt in meinem Kopf.)

Answer 1

Es gibt viele Beispiele mathy hier, aber Sie wollten eine realen Welt Beispiel so mit einem bisschen denken, dies ist vielleicht das Beste, was ich anbieten kann:

Sie eine Person finden, die eine bestimmte contageous Infektion zugezogen hat, die nicht tödlich ist, und Korrekturen sich schnell (Typ A), mit Ausnahme eines in 5 Personen (Wir werden diese Art B nennen), die mit ihm dauerhaft infiziert werden und zeigt keine Symptome und wirkt lediglich einen Spreizer.

Das schafft ziemlich ärgerlich Wellen von Chaos, wenn überhaupt Typ B eine Vielzahl von Typ A infiziert.

Ihre Aufgabe ist es, alle Typ Bs aufzuspüren und immunisieren sie das Rückgrat der Krankheit zu stoppen. Leider tho, man kann eine flächendeckende Heilung für alle verwalten, weil die Menschen, die typeAs sind auch tödlich allergisch auf die Heilung, die für den Typ B arbeitet.

Die Art und Weise Sie dies tun würde, würde soziale Entdeckung sein, eine infizierte Person (Typ A) gegeben, wählen alle ihre Kontakte in der letzten Woche, jeden Kontakt auf einem Haufen Markierung. Wenn Sie eine Person testen infiziert ist, füge sie die „Follow-up“ Warteschlange. Wenn eine Person ein Typ B ist, füge sie das „Follow-up“ am Kopf (weil Sie diese schnell stoppen wollen).

eine bestimmte Person Nach der Verarbeitung, wählen Sie die Person aus der Vorderseite der Warteschlange und Immunisierung anwenden, wenn nötig. Holen Sie sich alle ihre Kontakte, die zuvor nicht besuchte, und dann testen, um zu sehen, ob sie infiziert sind.

Wiederholen, bis die Warteschlange der Infizierten 0 wird, und dann für einen weiteren Ausbruch warten ..

(Ok, das ist ein bisschen iterative, aber sein ein iterativer Weise ein rekursive Problem zu lösen, in diesem Fall erscheinen Breite Traversal einer Bevölkerungsbasis wahrscheinlich Wege, um Probleme zu entdecken versuchen, und außerdem iterative Lösungen sind oft schneller und effektiver, und ich Rekursion zwanghaft entfernen überall so viel sein instinktiven worden. .... dammit!)

Answer 2

Ein Beispiel aus der Praxis der Rekursion

Answer 3

Wie wäre es alles eine Verzeichnisstruktur im Dateisystem beteiligt sind. Recursively das Auffinden von Dateien, Löschen von Dateien, Erstellen von Verzeichnissen, etc.

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

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());
            }
        }       
    }

}

Answer 4

Quicksort , Mergesort und die meisten anderen N-log N Art.

Answer 5

Matt Dillards Beispiel ist gut. Allgemeiner kann jeder Fuß eines Baumes im Allgemeinen sehr leicht durch Rekursion behandelt werden. Zum Beispiel Kompilieren Parse-Bäume, über XML oder HTML zu Fuß, etc.

Answer 6

Rekursion wird oft in Implementierungen des Backtracking-Algorithmus . Für eine "real-world" Anwendung dieser, wie über einen Sudoku Solver ?

Answer 7

Rekursion geeignet ist, wenn ein Problem gelöst werden kann es in Teilprobleme unterteilt, kann man erkennen, den gleichen Algorithmus sie zur Lösung verwenden. Algorithmen, die auf Bäumen und sortierte Listen sind eine logische Folge. Viele Probleme in der algorithmischen Geometrie (und 3D-Spiele) können rekursiv Binary Space Partitioning Verwendung gelöst werden (BSP ) Bäume, Fettunterteilungen , oder auf andere Weise die Welt in Teilabschnitte aufgeteilt wird.

Rekursion ist auch geeignet, wenn Sie versuchen, die Richtigkeit eines Algorithmus zu gewährleisten. Bei einer Funktion, die unveränderlich Eingaben nimmt und gibt ein Ergebnis, das eine Kombination von rekursiven und nicht-rekursive Aufrufen an den Eingängen ist, dann ist es in der Regel einfach die Funktion korrekt ist (oder nicht) mit Hilfe mathematische Induktion zu beweisen. Es ist oft schwer zu dies mit einer iterativen Funktion zu tun oder mit Eingaben, die mutieren können. Dies kann nützlich sein, wenn sie mit finanziellen Berechnungen und anderen Anwendungen zu tun, wo Richtigkeit sehr wichtig ist.

Answer 8

Sicher, dass viele Compiler gibt Rekursion stark verwenden. Computersprachen sind selbst von Natur aus rekursiv (das heißt, können Sie ‚if‘ Anweisungen in anderen einbetten ‚if‘ Aussagen, usw.).

Answer 9

Die Deaktivierung / Einstellung schreibgeschützt für alle Kinder steuert in einem Container Kontrolle. Ich musste das tun, weil einige der Kinder Kontrollen Behälter 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);
    }
}

Answer 10

Famous Eval / Apply-Zyklus von
_{(Quelle: mit.edu )}

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 gelten:

(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-Sequenz:

(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

Answer 11

Rekursion in Dingen wie BSP Bäume verwendet wird für die Kollisionserkennung in der Spielentwicklung (und anderen ähnlichen Bereichen).

Answer 12

Die Menschen sortieren oft Stapel von Dokumenten eine rekursive Methode. Zum Beispiel vorstellen, dass Sie 100 Dokumente mit Namen auf ihnen zu sortieren. Der erste Platz Dokumente in Stapeln durch den ersten Buchstaben, dann jeden Stapel sortieren.

Worte im Wörterbuch nachschlagen oft durch eine binären-search-ähnliche Technik durchgeführt wird, die rekursiv ist.

In Organisationen geben Bosse oft Befehle an Abteilungsleiter, der wiederum Befehle an Manager geben, und so weiter.

Answer 13

Parser und Compiler können in einem rekursiven-Abstiegsverfahren geschrieben werden. Nicht der beste Weg, es zu tun, als Werkzeuge wie lex / yacc erzeugt schneller und effizienten Parser, aber vom Konzept her einfach und leicht zu implementieren, so bleiben sie häufig.

Answer 14

Reale Welt Anforderung Seit kurzem bin ich:

Voraussetzung. A: Implementieren Sie diese Funktion nach Anforderung Einer durchaus Verständnis

Answer 15

Rekursion auf Probleme (Situationen) angewandt, wo Sie es brechen können (es reduziert) in kleinere Teile, und jeder Teil (e) sieht ähnlich aus wie das ursprüngliche Problem.

Gute Beispiele, wo die Dinge, die kleineren Teile ähnlich selbst enthalten sind:

• Baumstruktur (ein Zweig ist wie ein Baum)
• Listen (Teil einer Liste ist noch eine Liste)
• Container (russische Puppen)
• Sequenzen (Teil einer Sequenz sieht aus wie die nächste)
• Gruppen von Objekten (eine Untergruppe ist noch eine Gruppe von Objekten)

Rekursion ist eine Technik zu halten, um das Problem Abbau in immer kleinere Stücke, bis eines dieser Stücke werden klein genug, um ein Stück-of-Kuchen zu sein. Natürlich, nachdem Sie sie nach oben brechen, haben Sie dann, um die Ergebnisse „Stich“ wieder zusammen in der richtigen Reihenfolge eine Gesamtlösung des ursprünglichen Problems zu bilden.

Einige rekursiven Sortieralgorithmen, Tree-Walking-Algorithmen, Map / Reduce-Algorithmen, Teile-und-Herrsche sind Beispiele für diese Technik.

In der Computerprogrammierung, die meisten Stack-basierte Call-Rückgabetyp Sprachen bereits die Funktionen für die Rekursion eingebaut haben: das heißt

• brechen das Problem in kleinere Stücke ==> nennen sich auf eine kleinere Teilmenge der ursprünglichen Daten),
• zu verfolgen, wie die Stücke geteilt ==> Call-Stack,
• Stich die Ergebnisse zurück ==> Stack-basierte Rückkehr

Answer 16

Ich habe ein System, das reine Endrekursion an einigen Stellen verwendet einen Zustand zu simulieren Maschine.

Answer 17

Einige große Beispiele für Rekursion sind in funktionalen Programmierung Sprachen. In funktionalen Programmiersprachen ( Erlang , Haskell , ML / OCaml / F # , etc.), ist es sehr häufig jede Listenverarbeitung Verwendung Rekursion haben.

Wenn Sie mit Listen in typischen zwingend notwendig, OOP-Stil Sprachen zu tun, dann ist es sehr häufig Listen zu sehen, wie verkettete Listen implementiert ([item1 -> item2 -> item3 -> item4]). Doch in einigen funktionalen Programmiersprachen, finden Sie die Listen selbst rekursiv durchgeführt werden, wo der „Kopf“ der Liste zeigt auf den ersten Eintrag in der Liste, und der „Schwanz“ verweist auf eine Liste, um den Rest der Elemente enthält ( [item1 -> [item2 -> [item3 -> [item4 -> []]]]]). Es ist ziemlich kreativ in meiner Meinung nach.

Diese Handhabung von Listen, wenn sie mit Pattern Matching kombiniert, ist sehr mächtig. Sagen wir, ich möchte eine Liste von Zahlen fassen:

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

Das sagt im Wesentlichen: „Wenn wir mit einer leeren Liste genannt wurden, 0 zurück“ (so dass uns die Rekursion brechen), sonst gibt den Wert des Kopfes + den Wert der Summe mit den übrigen Elementen genannt (daher unsere Rekursion) .

Zum Beispiel könnte ich eine Liste haben URLs , ich glaube, auseinander brechen alle URLs jeweils URL-Links zu, und dann habe ich die Gesamtzahl der Verbindungen zu / von allen URLs reduzieren zu generieren „Werte“ für eine Seite (ein Ansatz, dass Google nimmt mit PageRank und dass Sie in der ursprünglichen MapReduce Papier). Sie können dies tun, auch Wort zählt in einem Dokument zu erzeugen. Und viele, viele, viele andere Dinge auch.

Sie können diese Funktionsmuster auf jede Art von MapReduce erweitern Code, in dem Sie eine Einnahme kann Liste von etwas, transformierende es, und die Rückkehr etwas anderes (ob eine andere Liste, oder ein Zip-Befehl auf der Liste).

Answer 18

XML oder durchquert alles, was ein Baum ist. Obwohl ich viel um ehrlich zu sein, ziemlich nie Rekursion in meinem Job verwenden.

Answer 19

Feedback-Schleifen in einer hierarchischen Organisation.

Top Chef sagt Top-Führungskräfte Feedback von jedem im Unternehmen zu sammeln.

Jede Exekutive sammelt seine / ihre direkten Berichte und sagt ihnen Feedback von ihren direkten Vorgesetzten zu sammeln.

Und auf der ganzen Linie.

Menschen ohne direkte Berichte - der Blattknoten in dem Baum -. Gibt ihr Feedback

Das Feedback fährt zurück auf den Baum mit jedem Manager seines / ihr eigenes Feedback hinzufügen.

Schließlich alle Feedback macht es wieder bis zum oberen Chef.

Dies ist die natürliche Lösung, weil die rekursive Methode auf jeder Ebene Filterung ermöglicht - der Zusammentrag von Duplikaten und das Entfernen von offensiven Feedback. Der Top-Chef könnte eine globale E-Mail senden und jeden Mitarbeiter Bericht Feedback hat direkt zurück zu ihm / ihr, aber es gibt die „man die Wahrheit nicht umgehen kann“ und die Probleme „Sie sind gefeuert“ , so Rekursion arbeitet hier am besten.

Answer 20

Angenommen, Sie für eine Website ein CMS bauen, wo Sie Ihre Seiten in einer Baumstruktur sind, etwa mit der Wurzel der Home-Seite zu sein.

Nehmen wir auch Ihre {user | Kunde | Kunden | Chef} Anfragen, die Sie auf jeder Seite einen Brotkrumen platzieren zu zeigen, wo Sie in dem Baum sind

.

Für jede gegebene Seite n, werden Sie möglicherweise an die Mutter von n gehen möchten, und seine Eltern, und so weiter, rekursiv eine Liste der Knoten wieder auf die Wurzel des Seitenbaums zu bauen.

Natürlich sind Schlagen Sie die db mehrmals pro Seite in diesem Beispiel, so können Sie einige SQL-Aliasing verwenden möchten, wo Sie Seitentabelle als aufblicken und Seiten Tabelle wieder als b, und eine Verknüpfung .id mit b.parent, so dass Sie die Datenbank tun die rekursive Joins machen. Es ist schon eine Weile, so dass meine Syntax ist wahrscheinlich nicht hilfreich.

Dann wieder, mögen Sie vielleicht nur dies nur einmal berechnen und speichern mit der Seite Datensatz, Aktualisierung es nur, wenn Sie die Seite bewegen. Das wäre wahrscheinlich effizienter sein.

Wie auch immer, das ist mein $ .02

Answer 21

Sie haben eine Organisationsstruktur, die N Ebenen tief ist. Mehrere der Knoten überprüft, und Sie wollen nur diese Knoten erweitern aus, die überprüft wurden.

Dies ist etwas, das ich eigentlich codiert. Es ist schön und einfach mit Rekursion.

Answer 22

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

es ohne Rekursion lösen würde eine Menge unnötigen Code erfordern. Das Problem mit Rekursion ist, dass es nicht leicht zu folgen ist, was passiert. Sie haben wirklich zu konzentrieren, wenn nach dem Ablauf der Ausführung. Aber wenn es funktioniert der Code ist elegant und effektiv.

Answer 23

Die Berechnungen für die Bereiche Finanzen / Physik, wie die Verbindung mittelt.

Answer 24

• Das Parsen eines XML Datei.
• Effiziente Suche in mehrdimensionalen Räumen. Z.B. Quad-Bäume in 2D, Oct-Bäume in 3D, kd-Bäume, etc.
• Hierarchical Clustering.
• Kommen Sie, daran zu denken, jede hierarchische Struktur durchqueren sich natürlich verleiht Rekursion.
• Template Metaprogrammierung in C ++, wo es keine Schleifen und Rekursion ist der einzige Weg.

Answer 25

Das Parsen einen Baum von Kontrollen in Windows Forms oder WebForms (.NET Windows Forms / < a href = "http://en.wikipedia.org/wiki/ASP.NET" rel = "nofollow noreferrer"> ASP.NET ).

Answer 26

Das beste Beispiel, das ich weiß, ist, quicksort , es viel einfacher, mit Rekursion ist. Schauen Sie sich auf:

shop.oreilly.com/product/9780596510046.do

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

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

Answer 27

Telefon- und Kabelgesellschaften halten ein Modell ihrer Verdrahtungstopologie, die in der Tat ein großes Netzwerk oder ein Diagramm ist. Rekursion ist ein Weg, um dieses Modell zu durchqueren, wenn Sie alle Eltern oder alle untergeordneten Elemente finden möchten.

Da Rekursion von einem Verarbeitungs- und Speichern perspektivischen teuer ist, wird dieser Schritt üblicherweise ausgeführt, wenn nur die Topologie geändert wird, und das Ergebnis wird in einem modifizierten vorbestellten Listenformat gespeichert.

Answer 28

Induktive Argumentation, der Prozess der Begriffsbildung, ist rekursiv in der Natur. Ihr Gehirn tut es die ganze Zeit, in der realen Welt.

Answer 29

Ditto den Kommentar über Compiler. Die abstrakte Syntaxbaum Knoten eignen sich natürlich Rekursion. Alle rekursive Datenstrukturen (verkettete Listen, Bäume, Grafiken, etc.) werden ebenfalls leichter mit Rekursion behandelt. Ich glaube, dass die meisten von uns nicht bekommen Rekursion viel zu benutzen, wenn wir wegen der verschiedenen Arten von Problemen der realen Welt aus der Schule sind, aber es ist gut, es als eine Option zu beachten.

Answer 30

Die Multiplikation der natürlichen Zahlen ist ein reales Beispiel der 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