Rekursion ohne Fakultät, Fibonacci - Zahlen usw

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.

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

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.

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.

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)

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.

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:] )

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

• Türme von Hanoi
• Acht Königinnen

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)

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

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

Ein Palindrom-Detektor:

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

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

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.

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

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.

Familienbeziehungen sind gute Beispiele, weil jeder sie intuitiv versteht:

ancestor(joe, me) = (joe == me) 
                    OR ancestor(joe, me.father) 
                    OR ancestor(joe, me.mother);

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.

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.

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.