/home/bakera/wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Zuletzt angesehen: • rekursion
schule:rekursion

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen RevisionVorhergehende Überarbeitung
Nächste Überarbeitung		Vorhergehende Überarbeitung
schule:rekursion [2019-12-09 15:33] – [Beispiel: Anzahl Elemente einer Liste] marco.bakeraschule:rekursion [2024-01-20 09:39] (aktuell) – mv pintman
Zeile 1: Zeile 1:
-====== Rekursion ====== +Verschoben nach [[edu:Rekursion]].
- +
-{{:schule:rekursion_animation.gif?direct|}} +
- +
-Die Rekursion beschreibt in der Programmierung das Phänomen, wenn eine Methode sich selbst aufruft.  +
- +
-**Ein Algorithmus ist rekursiv, wenn er mit Hilfe einfacher Varianten von sich selbst beschrieben wird.** +
- +
-<code python> +
-loese(<Problem>): +
-   ... +
-   loese(<einfacheres Problem>) +
-   ... +
-</code> +
- +
-Das sieht zunächst seltsam aus, kann sich aber in vielen Situationen als nützlich erweisen.  +
- +
-===== Allgemeiner Aufbau ===== +
- +
-Eine rekursive Funktion oder Methode ist häufig nach einem ganz bestimmten Muster aufgebaut. +
- +
-<code python> +
-REKURSIVE_METHODE(<Problem>): +
-  if <das Problem ist leicht>: +
-    <löse das Problem> +
-  else: +
-    <mache das Problem leichter> +
-    REKURSIVE_METHODE(<leichteres Problem>) +
-</code> +
- +
-**Jeder rekursive Algorithmus muss eine Abbruchbedingung enthalten.** +
- +
-===== Beispiel: Anzahl Elemente einer Liste ===== +
- +
- +
-Ein Beispiel soll dies veranschaulichen: Wir wollen die Anzahl der Elemente in einer Liste ermitteln. Ein gewöhnliches iteratives Verfahren könnte wie folgt aussehen. +
- +
-<code python> +
-def anzahl(liste): +
-  anzahl = 0 +
-  for element in liste: +
-    anzahl = anzahl + 1 +
-     +
-  return anzahl +
-</code> +
- +
-Ein rekursiver Algorithmus würde das Problem wie folgt lösen: +
- +
-<code python> +
-def anzahl(liste): +
-  if liste ist leer: +
-    return 0 +
- +
-  else: +
-    liste_kleiner = liste[1:]  #  entferne erstes Element +
-    return 1 + anzahl(liste_kleiner) +
-</code> +
- +
- +
-===== Übung Ausgabe ===== +
- +
-Alle Elemente einer Liste sollen mit der Methode ''ausgeben(liste)'' ausgegeben werden. Nutze ein rekursives Verfahren. Überlege zunächst, für welche Liste das Problem leicht lösbar ist. +
- +
-<code python> +
- +
->>> ausgeben([1,2,3]) +
-1 +
-2 +
-3 +
->>> ausgeben([1]) +
-1 +
-</code> +
-===== Übung rekursive Suche ===== +
- +
-Wie sieht ein rekursiver Algorithmus ''suche(n, liste)'' aus, der ein Element in einer Liste sucht und True oder False zurückgibt, wenn das Element in der Liste vorhanden ist oder nicht? +
- +
-<code> +
->>> suche(1, [1,2,3]) +
-True +
- +
->>> suche(2, [1,2,3]) +
-True +
- +
->>> suche(3, [1,2,3]) +
-True +
- +
->>> suche(4, [1,2,3]) +
-False +
-</code> +
- +
-===== Übung Filtern ===== +
- +
-Schreibe einen rekursiven Algorithmus, der alle geraden Zahlen aus einer Liste zurück gibt. +
- +
-<code> +
->>> gerade([1,2,3]) +
-[2] +
- +
->>> gerade([1,2,3,4]) +
-[4, 2] +
- +
->>> gerade([1,3,4]) +
-[4] +
- +
->>> gerade([]) +
-[] +
- +
-</code> +
- +
-===== Übung Streckenalgorithmus ===== +
- +
-{{:schule:prog:strecke_zwischen_zwei_punkten.png?direct|}} +
- +
-In den [[https://tbs1.de/owncloud/index.php/s/al3BJaHnhXS7WlM|Materialien]] findest du Informationen darüber, wie eine Strecke zwischen zwei Punkten A und B mit einem rekursiven Verfahren auf dem Bildschirm ausgegeben werden kann.  +
- +
-Wie sieht der einfache Fall aus? +
- +
-Vervollständige den folgenden Algorithmus zum Zeichnen einer Strecke. +
- +
-<code python> +
-from tkinter import * +
- +
-class App: +
-    def __init__(self): +
-        fenster = Tk() +
-         +
-        self.canv = Canvas(fenster, width=200, height=200) +
-        self.canv.pack() +
- +
-        self.strecke(10, 10, 150, 180) +
-        fenster.mainloop() +
- +
-    def markiere(self, x, y): +
-        self.canv.create_rectangle(x,y,x+1,y+1) +
- +
- +
-    def strecke(self, ax, ay, bx, by): +
-        # Hier muss eine Strecke rekursiv gezeichnet werden +
-        # if Punkte a und b benachbart: +
-        #   zeichne Pixel a und b +
-        # else: +
-        #   berechne mittelpunkt m +
-        #   zeichne Strecke von a bis m +
-        #   zeichne Strecke von m bis b +
-        pass +
- +
-app = App() +
-</code> +
- +
-===== Übung Kochkurve ===== +
- +
-{{:schule:prog:kochkurve.png|}} +
- +
-Eine weitere Anwendung von Rekursion findet sich in selbst-ähnlichen Kurven aus der Mathematik und der Natur. Die [[wpde>Koch-Kurve]] ist eine solche Figur, die mit Turtle-Grafiken erstellt werden kann. +
- +
-Verwende die folgende Vorlage und zeichne damit eine Kochkurve. +
- +
-<code python kockurve.py> +
-import turtle +
- +
-""" +
-Die Turtle kann mit folgenden Befehlen bewegt werden: +
- +
-tutle.forward(distanz) bewegt die Schildkröte in Blickrichtung +
-turtle.right(winkel) dreht die Schildkröte nach rechts. +
-tirtle.left(winkel) dreht die Schildkröte nach links. +
-""" +
- +
-def kochkurve(laenge, tiefe): +
-    """Zeichnet eine Kochkurve. +
-    laenge beschreibt die Länge des aktuellen Streckenabschnitts +
-    tiefe steht für die Rekursionstiefe.""" +
-    if tiefe == 0: +
-        """Gehe nach vorn.""" +
-    else: +
-        """Zeichne eine Kochkurve, drehe nach links, zeichne wieder eine Kurve,  +
-        drehe nach rechts, zeichne erneut, drehe nach links und zeichne den Schluss.  +
-        _/\_ """ +
- +
-# Starte das Programm +
-turtle.reset() +
-turtle.speed(5) +
- +
-kochkurve(300, 2) +
- +
-</code> +
- +
-===== Übung Grundrechenarten ===== +
- +
-Auch die Grundrechenarten ''+'' und ''*'' lassen sich rekursiv beschreiben: +
- +
-    add(0, m) = 0 + m = m +
-    add(n, m) = n + m = ((n-1) + m) +1 +
- +
-    mult(0, m) = 0 * m = 0 +
-    mult(n, m) = n *m = (n-1)*m + m = add( mult(n-1, m), m) +
-     +
-Programmiere die Methoden ''add'' und ''mult''. +
-===== Übung Türme von Hanoi ===== +
- +
-{{:schule:tower_of_hanoi.gif?direct|}} +
- +
-Unterschiedlich große Scheiben sind der Größe nach auf einem Stab platziert. Es gibt drei Stäbe A, B und C. Alle Scheiben müssen von Stab A nach C bewegt werden. Es darf immer nur eine Scheibe bewegt werden. Eine Scheibe darf nur auf eine größeren Scheibe platziert werden. +
- +
-Am besten probierst du das [[http://www.hirnhuepf.de/interaktiv/hanoi.html|Spiel]] einmal selbst aus. +
- +
-Ein möglicher Algorithmus, um das Problem zu lösen. +
- +
-<code> +
-bewege(Zahl i, Stab a, Stab b, Stab c) +
-    if i == 0: +
-       <mache nichts> +
-    else: +
-       bewege(i-1, a, c, b) +
-       verschiebe oberste Scheibe von a nach c +
-       bewege(i-1, b, a, c) +
-</code> +
- +
-Ein [[https://youtu.be/2SUvWfNJSsM|Video]] beschreibt den Zusammenhang zwischen Binärzahlen und den Zügen der Scheiben des Hanoi-Spiels. +
- +
-===== Übung Flachklopfen ===== +
- +
-Die Methode ''flach_klopfen'' nimmt eine Liste aus Listen entgegen und gibt eine flache Liste zurück, die nur noch die Elemente der Einzellisten enthält. Diese Listen könnten z.B. Verzeichnisse und Dateien in diesen Verzeichnissen in einem Dateisystem darstellen. Jeder Liste innerhalb einer Liste steht dann für ein Unterverzeichnis. +
- +
-<code> +
->>> flach_klopfen([1,2,3]) +
-[1,2,3] +
- +
->>> flach_klopfen([1,[2],3]) +
-[1,2,3] +
- +
->>> flach_klopfen([[],1,2,3])) +
-[1,2,3] +
- +
->>> flach_klopfen([1,[2,[3]]]) +
-[1,2,3] +
- +
->>> flach_klopfen([1,[], [2, 3],[]]) +
-[1,2,3] +
-</code> +
- +
-===== Übung umdrehen ===== +
- +
-Die Methode ''umdrehen'' nimmt eine Liste entgegen und dreht diese Liste um, so dass anschließend alle Elemente in umgedrehter Reihenfolge in der Liste auftauchen. +
- +
-<code> +
->>> umdrehen([]) +
-[] +
->>> umdrehen([1,2,3]) +
-[3, 2, 1] +
-</code> +
- +
-===== Live Coding mit Fluxus ===== +
- +
-Die Programmierumgebung [[live_coding#teil_1fluxus|Fluxus]] kann für das Live-Coding verwendet werden und nutzt in der Programmiersprache rekursive Mechanismen. +
- +
-<html> +
-<iframe width="560" height="315" src="https://www.youtube.com/embed/sS7WpYWm8PQ?rel=0" frameborder="0" allowfullscreen></iframe> +
-</html> +
- +
- +
-===== Probleme rekursiver Algorithmen ===== +
- +
-Rekursive Algorithmen sind häufig elegant und kurz, manchmal aber auch schwer zu verstehen. Nicht immer sind sie das richtige Mittel der Wahl, obwohl manche Programmiersprachen vollständig auf Rekursion setzen. +
- +
-  * Hoher Speicherplatzbedarf - Jeder Aufruf benötigt Speicherplatz für lokale Variablen +
-  * Unendliche Rekursion - Wenn man nicht aufpasst, enden die rekursiven niemals. +
-===== Rekursive Abkürzungen ===== +
- +
-Auch in anderen Gebieten der Informatik hat sich die Rekursion etabliert. So gibt es [[wpde>Rekursives Akronym|rekursive Abkürzungen]]:  +
- +
-  * PHP (PHP Hypertext Preprocessor) +
-  * LAME (LAME Ain’t an Mp3 Encoder) +
-  * WINE (WINE Is Not an Emulator) +
-  * YAML (YAML Ain't Markup Language) +
- +
-===== Links ===== +
- +
-  * [[https://tbs1.de/owncloud/index.php/s/al3BJaHnhXS7WlM|Materialien]] +
-  * [[https://www.youtube.com/watch?v=gYpMz63WAjM|Ein Kran trägt einen Kran trägt einen Kran (Video)]]+
schule/rekursion.1575902036.txt.gz · Zuletzt geändert: 2019-12-09 15:33 von marco.bakera