schule:rekursion
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen RevisionVorhergehende ÜberarbeitungNächste Überarbeitung | Vorhergehende ÜberarbeitungNächste ÜberarbeitungBeide Seiten der Revision | ||
schule:rekursion [2016-12-15 15:23] – [Übung Türme von Hanoi] marco.bakera | schule:rekursion [2021-06-10 07:13] – [Beispiel: Anzahl Elemente einer Liste] pintman | ||
---|---|---|---|
Zeile 21: | Zeile 21: | ||
<code python> | <code python> | ||
- | rekursive_Methode(< | + | REKURSIVE_METHODE(< |
if <das Problem ist leicht>: | if <das Problem ist leicht>: | ||
<löse das Problem> | <löse das Problem> | ||
else: | else: | ||
<mache das Problem leichter> | <mache das Problem leichter> | ||
- | | + | |
</ | </ | ||
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) | ||
</ | </ | ||
+ | |||
+ | Erinnerung: mit '' | ||
+ | Wird a oder b weggelassen, | ||
Zeile 112: | Zeile 115: | ||
{{: | {{: | ||
- | In den [[https:// | + | 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 |
+ | |||
+ | <code python> | ||
+ | from tkinter import Tk, Canvas | ||
+ | |||
+ | class App: | ||
+ | def __init__(self): | ||
+ | fenster = Tk() | ||
+ | |||
+ | self.canv = Canvas(fenster, | ||
+ | self.canv.pack() | ||
+ | |||
+ | self.strecke(10, | ||
+ | fenster.mainloop() | ||
+ | |||
+ | def markiere(self, | ||
+ | self.canv.create_rectangle(x, | ||
+ | |||
+ | |||
+ | def strecke(self, | ||
+ | # Hier muss eine Strecke rekursiv gezeichnet werden | ||
+ | # if Punkte a und b benachbart: | ||
+ | # | ||
+ | # else: | ||
+ | # | ||
+ | # | ||
+ | # | ||
+ | pass | ||
+ | |||
+ | app = App() | ||
+ | </ | ||
+ | |||
+ | ===== Übung Kochkurve ===== | ||
+ | |||
+ | {{: | ||
+ | |||
+ | Eine weitere Anwendung von Rekursion findet sich in selbst-ähnlichen Kurven aus der Mathematik und der Natur. Die [[wpde> | ||
+ | |||
+ | 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, | ||
+ | """ | ||
+ | laenge beschreibt die Länge des aktuellen Streckenabschnitts | ||
+ | tiefe steht für die Rekursionstiefe.""" | ||
+ | if tiefe == 0: | ||
+ | """ | ||
+ | else: | ||
+ | """ | ||
+ | drehe nach rechts, zeichne erneut, drehe nach links und zeichne den Schluss. | ||
+ | _/\_ """ | ||
+ | |||
+ | # Starte das Programm | ||
+ | turtle.reset() | ||
+ | turtle.speed(5) | ||
+ | |||
+ | kochkurve(300, | ||
+ | |||
+ | </ | ||
===== Übung Grundrechenarten ===== | ===== Übung Grundrechenarten ===== | ||
Zeile 141: | Zeile 212: | ||
< | < | ||
bewege(Zahl i, Stab a, Stab b, Stab c) | bewege(Zahl i, Stab a, Stab b, Stab c) | ||
- | if i > 0: | + | if i == 0: |
+ | < | ||
+ | else: | ||
| | ||
| | ||
| | ||
</ | </ | ||
+ | |||
+ | Ein [[https:// | ||
+ | |||
+ | ===== Übung Flachklopfen ===== | ||
+ | |||
+ | Die Methode '' | ||
+ | |||
+ | < | ||
+ | >>> | ||
+ | [1,2,3] | ||
+ | |||
+ | >>> | ||
+ | [1,2,3] | ||
+ | |||
+ | >>> | ||
+ | [1,2,3] | ||
+ | |||
+ | >>> | ||
+ | [1,2,3] | ||
+ | |||
+ | >>> | ||
+ | [1,2,3] | ||
+ | </ | ||
+ | |||
+ | ===== Übung umdrehen ===== | ||
+ | |||
+ | Die Methode '' | ||
+ | |||
+ | < | ||
+ | >>> | ||
+ | [] | ||
+ | >>> | ||
+ | [3, 2, 1] | ||
+ | </ | ||
+ | |||
+ | ===== Live Coding mit Fluxus ===== | ||
+ | |||
+ | Die Programmierumgebung [[live_coding# | ||
+ | |||
+ | < | ||
+ | <iframe width=" | ||
+ | </ | ||
+ | |||
+ | |||
===== Probleme rekursiver Algorithmen ===== | ===== Probleme rekursiver Algorithmen ===== | ||
Zeile 152: | Zeile 269: | ||
* 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> | ||
+ | |||
+ | * 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:// | ||
* [[https:// | * [[https:// |
schule/rekursion.txt · Zuletzt geändert: 2024-01-20 09:39 von pintman