Benutzer-Werkzeuge

Webseiten-Werkzeuge


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
Letzte ÜberarbeitungBeide Seiten der Revision
schule:rekursion [2017-01-26 14:48] – [Übung Flachklopfen] marco.bakeraschule:rekursion [2021-06-10 07:15] – [Beispiel: Anzahl Elemente einer Liste] pintman
Zeile 37: Zeile 37:
  
 <code python> <code python>
-anzahl(liste):+def anzahl(liste):
   anzahl = 0   anzahl = 0
   for element in liste:   for element in liste:
Zeile 48: Zeile 48:
  
 <code python> <code python>
-anzahl(liste):+def anzahl(liste):
   if liste ist leer:   if liste ist leer:
     return 0     return 0
  
   else:   else:
-    liste_kleiner = liste.entferneErstesElement()+    liste_kleiner = liste[1:]  #  entferne erstes Element
     return 1 + anzahl(liste_kleiner)     return 1 + anzahl(liste_kleiner)
 </code> </code>
 +
 +Erinnerung: mit ''liste[a:b]'' wird der Teil von Index a bis zum Index b-1 aus einer Liste ausgelesen. 
 +Wird a oder b weggelassen, werden der Anfang Anfang bzw. das Ende der Liste verwendet. Dies nennt man
 +[[https://www.learnbyexample.org/python-list-slicing/|list slicing]].
  
  
Zeile 112: Zeile 116:
 {{:schule:prog:strecke_zwischen_zwei_punkten.png?direct|}} {{: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. +Bei den 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? Wie sieht der einfache Fall aus?
  
-Vervollständige den Algorithmus in dem VisualStudio-Projekt entsprechend.+Vervollständige den folgenden Algorithmus zum Zeichnen einer Strecke. 
 + 
 +<code python> 
 +from tkinter import Tk, Canvas 
 + 
 +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 ===== ===== Übung Grundrechenarten =====
Zeile 171: Zeile 243:
 [1,2,3] [1,2,3]
 </code> </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 ===== ===== Probleme rekursiver Algorithmen =====
  
Zeile 177: Zeile 270:
   * Hoher Speicherplatzbedarf - Jeder Aufruf benötigt Speicherplatz für lokale Variablen   * Hoher Speicherplatzbedarf - Jeder Aufruf benötigt Speicherplatz für lokale Variablen
   * Unendliche Rekursion - Wenn man nicht aufpasst, enden die rekursiven niemals.   * 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 ===== ===== 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)]]   * [[https://www.youtube.com/watch?v=gYpMz63WAjM|Ein Kran trägt einen Kran trägt einen Kran (Video)]]
schule/rekursion.txt · Zuletzt geändert: 2024-01-20 09:39 von pintman