Rekursion ohne Fakultät, Fibonacci - Zahlen usw

47

Fast jeder Artikel, den ich über Rekursion finden kann, enthält Beispiele für Fakultäts- oder Fibonacci-Zahlen:

  1. Mathematik
  2. Nutzlos im wirklichen Leben

Gibt es einige interessante nicht-mathematische Codebeispiele , um die Rekursion zu lehren?

Ich denke an Divide-and-Conquer-Algorithmen, aber diese beinhalten normalerweise komplexe Datenstrukturen.

lazyCrab
quelle
26
Während Ihre Frage vollständig gültig ist, würde ich zögern, Fibonacci-Nummern anzurufen, die im wirklichen Leben unbrauchbar sind . Gleiches gilt für Fakultät .
Zach L
2
Der kleine Schemer ist ein ganzes Buch über Rekursion, in dem weder Fact noch Fib verwendet werden. junix-linux-config.googlecode.com/files/…
Eric Wilson
5
@Zach: Trotzdem ist eine Rekursion aufgrund der exponentiellen Laufzeit ein schrecklicher Weg, um Fibonacci-Zahlen zu implementieren .
Dan04
2
@ dan04: Rekursion ist eine schreckliche Möglichkeit, fast alles zu implementieren, da in den meisten Sprachen die Möglichkeit eines Stapelüberlaufs besteht.
R ..
5
@ dan04 es sei denn , Ihre Sprache ist intelligent genug , um Endrekursion Optimierung wie die meisten funktionalen Sprachen in welchem Fall es funktioniert gut zu implementieren
Zachary K

Antworten:

107

Verzeichnis- / Dateistrukturen sind das beste Beispiel für eine Verwendung für die Rekursion, da jeder sie versteht, bevor Sie beginnen, aber alles, was baumähnliche Strukturen umfasst, reicht aus.

void GetAllFilePaths(Directory dir, List<string> paths)
{
    foreach(File file in dir.Files)
    {
        paths.Add(file.Path);
    }

    foreach(Directory subdir in dir.Directories)
    {
        GetAllFilePaths(subdir, paths)
    }
}

List<string> GetAllFilePaths(Directory dir)
{
    List<string> paths = new List<string>();
    GetAllFilePaths(dir, paths);
    return paths;
}
pdr
quelle
1
Danke, ich denke, ich werde mit Dateisystem gehen. Es ist etwas Konkretes und kann für viele Beispiele aus der Praxis verwendet werden.
Synapse
9
Hinweis: Unix-Befehle schließen häufig die Option -r aus (z. B. cp oder rm). -r steht für rekursiv.
Deadalnix
7
man muss hier ein wenig vorsichtig sein, da in der realen Welt Dateisysteme eigentlich ein gerichteter Graph sind, nicht unbedingt ein Baum, wenn er vom Dateisystem unterstützt wird, können harte Links usw. Joins und Zyklen erzeugen
jk.
1
@jk: Verzeichnisse können nicht fest miteinander verbunden sein. Daher müssen einige Blätter, die möglicherweise an mehreren Stellen vorhanden sind, moduliert werden. Wenn Sie Symlinks ausschließen, handelt es sich bei den realen Dateisystemen um Bäume.
R ..
1
In einigen Dateisystemen gibt es andere Besonderheiten für Verzeichnisse, z. B. NTFS-Analysepunkte. Mein Punkt ist, dass Code, der sich dessen nicht bewusst ist, unerwartete Ergebnisse auf realen Dateisystemen haben kann
jk.
51

Suchen Sie nach Dingen, die Baumstrukturen betreffen. Ein Baum ist relativ einfach zu erfassen, und die Schönheit einer rekursiven Lösung wird viel früher sichtbar als bei linearen Datenstrukturen wie Listen.

Dinge, über die man nachdenken sollte:

  • Dateisysteme - das sind im Grunde Bäume; Eine nette Programmieraufgabe wäre, alle .jpg-Bilder unter einem bestimmten Verzeichnis und all seinen Unterverzeichnissen abzurufen
  • Vorfahren - Wenn Sie einen Stammbaum haben, finden Sie die Anzahl der Generationen, auf die Sie zugehen müssen, um einen gemeinsamen Vorfahren zu finden. oder prüfen Sie, ob zwei Personen im Baum derselben Generation angehören; oder überprüfe, ob zwei Personen im Baum legal heiraten dürfen (abhängig von der Gerichtsbarkeit :)
  • HTML-ähnliche Dokumente - Konvertieren Sie zwischen der seriellen (Text-) Darstellung eines Dokuments und einem DOM-Baum. Operationen für Teilmengen eines DOM ausführen (möglicherweise sogar eine Teilmenge von xpath implementieren?); ...

Diese beziehen sich alle auf reale Szenarien und können in Anwendungen von realer Bedeutung verwendet werden.

tdammers
quelle
Natürlich sollte beachtet werden, dass es fast immer besser ist, Zeiger / Verweise auf Eltern / nächste Geschwister / etc. Zu behalten, wenn Sie die Freiheit haben, Ihre eigene Baumstruktur zu entwerfen. in den Knoten, damit Sie ohne Rekursion über den Baum iterieren können.
R ..
1
Was haben Zeiger damit zu tun? Selbst wenn Sie Hinweise auf das erste Kind, das nächste Geschwister und das Elternteil haben, müssen Sie trotzdem irgendwie durch Ihren Baum gehen, und in einigen Fällen ist die Rekursion der praktikabelste Weg.
tdammers
40

https://stackoverflow.com/questions/105838/real-world-examples-of-recursion

  • Modellierung einer ansteckenden Infektion
  • Geometrie erzeugen
  • Verzeichnisverwaltung
  • Sortierung

https://stackoverflow.com/questions/2085834/how-did-you-practically-use-recursion

  • Raytracing
  • Schach
  • Parsing des Quellcodes (Sprachgrammatik)

https://stackoverflow.com/questions/4945128/what-is-a-good-example-of-recursion-other-than-generating-a-fibonacci-sequence

  • BST-Suche
  • Türme von Hanoi
  • Palindrom-Suche

https://stackoverflow.com/questions/126756/examples-of-recursive-functions

  • Gibt eine schöne englischsprachige Geschichte, die die Rekursion einer Gutenachtgeschichte veranschaulicht.
mskfisher
quelle
10
Während dies theoretisch die Frage beantworten mag, wäre es vorzuziehen , die wesentlichen Teile dieser Fragen und Antworten hier aufzunehmen und die Links als Referenz bereitzustellen. Wenn die Fragen jemals aus SO entfernt werden, ist Ihre Antwort völlig nutzlos.
Adam Lear
@Anna Nun, Benutzer können ihre Fragen nicht löschen. Wie wahrscheinlich ist das?
13.
4
@vemv Abstimmungen, Moderatoren, Regeln zu Themenänderungen löschen ... das kann passieren. In jedem Fall ist es besser, hier eine vollständigere Antwort zu haben, als einen Besucher von Anfang an auf vier verschiedene Seiten zu schicken.
Adam Lear
@Anna: Nach dieser Überlegung sollte in jede Frage, die als "genaues Duplikat" geschlossen wurde, die Antwort des Originals eingefügt werden. Diese Frage ist ein genaues Duplikat (der Fragen zu SO). Warum sollte sie eine andere Behandlung als exakt erhalten? Duplikate von Fragen zu Programmierern?
SF.
1
@SF Wenn wir es als Duplikat schließen könnten, würden wir, aber standortübergreifende Duplikate werden nicht unterstützt. Programmierer ist eine separate Site, daher würden Antworten hier im Idealfall SO als jede andere Referenz verwenden und nicht vollständig an sie delegieren. Es ist nicht anders als nur zu sagen "Ihre Antwort ist in diesem Buch" - technisch wahr, kann aber nicht sofort verwendet werden, ohne die Referenz zu konsultieren.
Adam Lear
22

Hier sind einige weitere praktische Probleme, die mir einfallen:

  • Zusammenführen, sortieren
  • Binäre Suche
  • Überqueren, Einfügen und Entfernen von Bäumen (wird hauptsächlich in Datenbankanwendungen verwendet)
  • Permutationsgenerator
  • Sudoku-Löser (mit Backtracking)
  • Rechtschreibprüfung (erneut mit Rückverfolgung)
  • Syntaxanalyse (zB ein Programm, das Präfix in Postfix-Notation konvertiert)
Daniel Scocco
quelle
11

QuickSort wäre der erste, der mir in den Sinn kommt. Die binäre Suche ist ebenfalls ein rekursives Problem. Darüber hinaus gibt es eine ganze Reihe von Problemen, bei denen Lösungen fast kostenlos herausfallen, wenn Sie mit der Rekursion beginnen.

Zachary K
quelle
3
Die binäre Suche wird oft als rekursives Problem formuliert, aber es ist trivial (und oft vorzuziehen), sie zwingend zu implementieren.
flauschiger
Abhängig davon, welche Sprache Sie verwenden, kann der Code explizit rekursiv oder imperativ oder rekursiv sein oder nicht. Es ist jedoch immer noch ein rekursiver Algorithmus, bei dem Sie das Problem in immer kleinere Teile aufteilen, um zur Lösung zu gelangen.
Zachary K
2
@Zachary: Algorithmen, die mit Tail-Rekursion implementiert werden können (wie die binäre Suche), befinden sich in einer grundlegend anderen Raumklasse als diejenigen, die eine echte Rekursion erfordern (oder Ihre eigenen Zustandsstrukturen mit ebenso teurem Raumbedarf). Ich finde es nicht vorteilhaft, wenn sie zusammen unterrichtet werden, als wären sie gleich.
R ..
8

In Python rekursiv definierte Sortierung.

def sort( a ):
    if len(a) == 1: return a
    part1= sort( a[:len(a)//2] )
    part2= sort( a[len(a)//2:] )
    return merge( part1, part2 )

Zusammenführen, rekursiv definiert.

def merge( a, b ):
    if len(b) == 0: return a
    if len(a) == 0: return b
    if a[0] < b[0]:
        return [ a[0] ] + merge(a[1:], b)
    else:
        return [ b[0] ] + merge(a, b[1:]) 

Lineare Suche, rekursiv definiert.

def find( element, sequence ):
    if len(sequence) == 0: return False
    if element == sequence[0]: return True
    return find( element, sequence[1:] )

Binäre Suche, rekursiv definiert.

def binsearch( element, sequence ):
    if len(sequence) == 0: return False
    mid = len(sequence)//2
    if element < mid: 
        return binsearch( element, sequence[:mid] )
    else:
        return binsearch( element, sequence[mid:] )
S.Lott
quelle
6

In gewissem Sinne geht es bei der Rekursion darum, Lösungen zu teilen und zu erobern, dh den Problemraum in einen kleineren zu unterteilen, um die Lösung für ein einfaches Problem zu finden, und dann in der Regel das ursprüngliche Problem zu rekonstruieren, um die richtige Antwort zu erhalten.

Einige Beispiele, bei denen es nicht um Mathematik geht, um Rekursion zu lehren (zumindest die Probleme, an die ich mich aus meiner Studienzeit erinnere):

Dies sind Beispiele für die Verwendung von Backtracking, um das Problem zu lösen.

Andere Probleme sind die Klassiker der Domäne der künstlichen Intelligenz: Verwendung der Tiefensuche, Pfadfindung, Planung.

Bei all diesen Problemen handelt es sich um eine Art "komplexe" Datenstruktur. Wenn Sie sie jedoch nicht mit Mathematik (Zahlen) unterrichten möchten, sind Ihre Auswahlmöglichkeiten möglicherweise eingeschränkter. Vielleicht möchten Sie mit einer grundlegenden Datenstruktur wie einer verknüpften Liste anfangen zu unterrichten. Zum Beispiel die natürlichen Zahlen mit einer Liste darstellen:

0 = leere Liste 1 = Liste mit einem Knoten. 2 = Liste mit 2 Knoten. ...

Definieren Sie dann die Summe zweier Zahlen in Bezug auf diese Datenstruktur wie folgt: Leer + N = N Knoten (X) + N = Knoten (X + N)

Gabriel
quelle
5

Die Türme von Hanoi eignen sich gut zum Erlernen der Rekursion.

Es gibt viele Lösungen im Web in vielen verschiedenen Sprachen.

Oded
quelle
3
Dies ist meiner Meinung nach ein weiteres schlechtes Beispiel. Zunächst einmal ist es unrealistisch; Es ist kein Problem, das die Leute tatsächlich haben. Zweitens gibt es einfache nicht-rekursive Lösungen. (Eine davon ist: Nummerieren Sie die Datenträger. Verschieben Sie niemals einen Datenträger auf einen Datenträger mit der gleichen Parität und machen Sie niemals den letzten Zug rückgängig. Wenn Sie diese beiden Regeln befolgen, lösen Sie das Rätsel mit der optimalen Lösung. Keine Rekursion erforderlich. )
Eric Lippert
5

Ein Palindrom-Detektor:

Beginnen Sie mit einer Zeichenfolge: "ABCDEEDCBA" Wenn Start- und Endzeichen gleich sind, überprüfen Sie "BCDEEDCB" usw.

NWS
quelle
6
Das ist auch trivial, ohne Rekursion zu lösen und, meiner Meinung nach, besser ohne sie zu lösen.
Blrfl
3
Einverstanden, aber OP Speziell nach Lehrbeispielen mit minimalem Einsatz von Datenstrukturen gefragt.
NWS
5
Es ist kein gutes Lehrbeispiel, wenn Ihre Schüler sofort eine nicht rekursive Lösung finden. Warum sollte jemand aufpassen, wenn Ihr Beispiel lautet: "Hier ist etwas Triviales, das mit einer Schleife zu tun hat. Jetzt zeige ich Ihnen ohne ersichtlichen Grund einen schwierigeren Weg."
Setzen Sie Monica
5

Ein binärer Suchalgorithmus klingt wie das, was Sie wollen.

Sardathrion
quelle
4

Wenn in funktionalen Programmiersprachen keine Funktionen höherer Ordnung verfügbar sind, wird anstelle von imperativen Schleifen eine Rekursion verwendet, um einen veränderlichen Zustand zu vermeiden.

F # ist eine unreine funktionale Sprache, die beide Stile erlaubt, also werde ich beide hier vergleichen. Die folgende Summe aller Zahlen in einer Liste.

Imperative Schleife mit veränderlicher Variable

let xlist = [1;2;3;4;5;6;7;8;9;10]
let mutable sum = 0
for x in xlist do
    sum <- sum + x

Rekursive Schleife ohne veränderlichen Zustand

let xlist = [1;2;3;4;5;6;7;8;9;10]
let rec loop sum xlist = 
    match xlist with
    | [] -> sum
    | x::xlist -> loop (sum + x) xlist
let sum = loop 0 xlist

Beachten Sie, dass diese Art der Aggregation wird in der Funktion höherer Ordnung erfasst List.foldund können so geschrieben werden List.fold (+) 0 xlistoder sogar noch einfacher mit der Komfortfunktion List.sumals nur List.sum xlist.

Stephen Swensen
quelle
du würdest mehr Punkte verdienen als nur +1 von mir. F # ohne Rekursion wäre sehr mühsam. Dies gilt umso mehr für Haskell, das NUR mit Rekursion keine Schleifenkonstrukte hat!
schoetbi
3

Ich habe die Rekursion beim Spielen von KI stark genutzt. Beim Schreiben in C ++ habe ich eine Reihe von ungefähr 7 Funktionen verwendet, die sich nacheinander aufrufen (wobei die erste Funktion die Option hat, alle diese Funktionen zu umgehen und stattdessen eine Kette von zwei weiteren Funktionen aufzurufen). Die letzte Funktion in beiden Ketten rief die erste Funktion erneut auf, bis die verbleibende Tiefe, die ich suchen wollte, auf 0 ging. In diesem Fall rief die letzte Funktion meine Bewertungsfunktion auf und gab die Punktzahl der Position zurück.

Die verschiedenen Funktionen ermöglichten es mir, einfach nach Spielerentscheidungen oder zufälligen Ereignissen im Spiel zu verzweigen. Ich habe immer Pass-by-Reference verwendet, da ich sehr große Datenstrukturen durchlief. Aufgrund der Struktur des Spiels war es jedoch sehr schwierig, bei meiner Suche einen "Rückgängig" -Zug zu machen In einigen Funktionen verwende ich die Übergabe von Werten, um meine ursprünglichen Daten unverändert zu lassen. Aus diesem Grund erwies sich die Umstellung auf einen schleifenbasierten Ansatz anstelle eines rekursiven Ansatzes als zu schwierig.

Eine sehr grundlegende Übersicht über diese Art von Programm finden Sie unter https://secure.wikimedia.org/wikipedia/en/wiki/Minimax#Pseudocode

David Stone
quelle
3

Ein wirklich gutes Beispiel aus dem Geschäftsleben ist die sogenannte "Stückliste". Dies sind die Daten, die alle Komponenten darstellen, aus denen ein fertiges Produkt besteht. Nehmen wir zum Beispiel ein Fahrrad. Ein Fahrrad hat Lenker, Räder, einen Rahmen usw. Und jede dieser Komponenten kann Unterkomponenten haben. Beispielsweise kann das Rad Speichen, einen Ventilschaft usw. aufweisen. Diese werden also normalerweise in einer Baumstruktur dargestellt.

Wenn Sie jetzt aggregierte Informationen zur Stückliste abfragen oder Elemente in einer Stückliste ändern möchten, greifen Sie häufig auf eine Rekursion zurück.

    class BomPart
    {
        public string PartNumber { get; set; }
        public string Desription { get; set; }
        public int Quantity { get; set; }
        public bool Plastic { get; set; }
        public List<BomPart> Components = new List<BomPart>();
    }

Und ein Beispiel für einen rekursiven Aufruf ...

    static int ComponentCount(BomPart part)
    {
        int subCount = 0;
        foreach(BomPart p in part.Components)
            subCount += ComponentCount(p);
        return part.Quantity * Math.Max(1,subCount);

    }

Offensichtlich würde die BomPart-Klasse viel, viel mehr Felder haben. Möglicherweise müssen Sie herausfinden, wie viele Kunststoffteile Sie haben, wie viel Arbeit Sie benötigen, um ein komplettes Teil zu erstellen usw. All dies kommt jedoch auf die Nützlichkeit von Rekursion an einer Baumstruktur zurück.

deepee1
quelle
Eine Stückliste kann ein gerichteter Grat sein, nicht ein Baum, z. B. kann dieselbe Schraubenspezifikation von mehr als einer Komponente verwendet werden.
Ian
-1

Familienbeziehungen sind gute Beispiele, weil jeder sie intuitiv versteht:

ancestor(joe, me) = (joe == me) 
                    OR ancestor(joe, me.father) 
                    OR ancestor(joe, me.mother);
Caleb
quelle
In welcher Sprache ist dieser Code geschrieben?
Törzsmókus
@ törzsmókus Keine bestimmte Sprache. Die Syntax ist ziemlich nah an C, Obj-C, C ++, Java und viele andere Sprachen, aber wenn Sie echten Code wollen , können Sie benötigen einen geeigneten Betreiber wie Ersatz ||für die OR.
Caleb
-1

Ein eher nutzloses, aber dennoch rekursives Inner Working Well ist rekursiv strlen():

size_t strlen( const char* str )
{
    if( *str == 0 ) {
       return 0;
    }
    return 1 + strlen( str + 1 );
}

Keine Mathematik - eine sehr einfache Funktion. Natürlich implementieren Sie es nicht rekursiv im realen Leben, aber es ist eine gute Demo der Rekursion.

scharfer Zahn
quelle
-2

Ein weiteres reales Rekursionsproblem, mit dem sich die Schüler möglicherweise befassen, besteht darin, einen eigenen Webcrawler zu erstellen, der Informationen von einer Website abruft und allen Links auf dieser Website (und allen Links von diesen Links usw.) folgt.

GregW
quelle
2
Dies wird im Allgemeinen besser durch eine Prozesswarteschlange als durch eine Rekursion im herkömmlichen Sinne erreicht.
flauschiger
-2

Ich habe ein Problem mit einem Rittermuster (auf einem Schachbrett) mit einem rekursiven Programm gelöst. Sie sollten den Ritter so bewegen, dass er jedes Feld mit Ausnahme einiger markierter Felder berührt.

Sie einfach:

mark your "Current" square
gather a list of free squares that are valid moves
are there no valid moves?
    are all squares marked?
        you win!
for each free square
    recurse!
clear the mark on your current square.
return.    

Viele Arten von "Vorausdenken" -Szenarien können bearbeitet werden, indem zukünftige Möglichkeiten in einem Baum wie diesem getestet werden.

Bill K
quelle