schule:rekursion
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen RevisionVorhergehende ÜberarbeitungNächste Überarbeitung | Vorhergehende Überarbeitung | ||
schule:rekursion [2016-12-15 15:22] – [Übung Grundrechenarten] Aufgabe marco.bakera | schule:rekursion [2024-01-20 09:39] (aktuell) – mv pintman | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ====== Rekursion ====== | + | Verschoben |
- | + | ||
- | {{: | + | |
- | + | ||
- | 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(< | + | |
- | ... | + | |
- | | + | |
- | ... | + | |
- | </ | + | |
- | + | ||
- | 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 | + | |
- | + | ||
- | <code python> | + | |
- | rekursive_Methode(< | + | |
- | if <das Problem ist leicht>: | + | |
- | <löse das Problem> | + | |
- | else: | + | |
- | <mache das Problem leichter> | + | |
- | rekursive_Methode(< | + | |
- | </ | + | |
- | + | ||
- | **Jeder rekursive Algorithmus muss eine Abbruchbedingung enthalten.** | + | |
- | + | ||
- | ===== Beispiel: Anzahl Elemente einer Liste ===== | + | |
- | + | ||
- | + | ||
- | Ein Beispiel soll dies veranschaulichen: | + | |
- | + | ||
- | <code python> | + | |
- | anzahl(liste): | + | |
- | anzahl = 0 | + | |
- | for element in liste: | + | |
- | anzahl = anzahl + 1 | + | |
- | + | ||
- | return anzahl | + | |
- | </ | + | |
- | + | ||
- | Ein rekursiver Algorithmus würde das Problem wie folgt lösen: | + | |
- | + | ||
- | <code python> | + | |
- | anzahl(liste): | + | |
- | if liste ist leer: | + | |
- | return 0 | + | |
- | + | ||
- | else: | + | |
- | liste_kleiner = liste.entferneErstesElement() | + | |
- | return 1 + anzahl(liste_kleiner) | + | |
- | </ | + | |
- | + | ||
- | + | ||
- | ===== Übung Ausgabe ===== | + | |
- | + | ||
- | Alle Elemente einer Liste sollen mit der Methode '' | + | |
- | + | ||
- | <code python> | + | |
- | + | ||
- | >>> | + | |
- | 1 | + | |
- | 2 | + | |
- | 3 | + | |
- | >>> | + | |
- | 1 | + | |
- | </ | + | |
- | ===== Übung rekursive Suche ===== | + | |
- | + | ||
- | Wie sieht ein rekursiver Algorithmus '' | + | |
- | + | ||
- | < | + | |
- | >>> | + | |
- | True | + | |
- | + | ||
- | >>> | + | |
- | True | + | |
- | + | ||
- | >>> | + | |
- | True | + | |
- | + | ||
- | >>> | + | |
- | False | + | |
- | </ | + | |
- | + | ||
- | ===== Übung Filtern ===== | + | |
- | + | ||
- | Schreibe einen rekursiven Algorithmus, | + | |
- | + | ||
- | < | + | |
- | >>> | + | |
- | [2] | + | |
- | + | ||
- | >>> | + | |
- | [4, 2] | + | |
- | + | ||
- | >>> | + | |
- | [4] | + | |
- | + | ||
- | >>> | + | |
- | [] | + | |
- | + | ||
- | </ | + | |
- | + | ||
- | ===== Übung Streckenalgorithmus ===== | + | |
- | + | ||
- | {{:schule: | + | |
- | + | ||
- | In den [[https:// | + | |
- | + | ||
- | Wie sieht der einfache Fall aus? | + | |
- | + | ||
- | Vervollständige den Algorithmus in dem VisualStudio-Projekt entsprechend. | + | |
- | + | ||
- | ===== Übung Grundrechenarten ===== | + | |
- | + | ||
- | Auch die Grundrechenarten '' | + | |
- | + | ||
- | 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 '' | + | |
- | ===== Übung Türme von Hanoi ===== | + | |
- | + | ||
- | {{: | + | |
- | + | ||
- | 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:// | + | |
- | + | ||
- | Ein möglicher Algorithmus, | + | |
- | + | ||
- | < | + | |
- | bewege (Zahl i, Stab a, Stab b, Stab c) | + | |
- | if i > 0: | + | |
- | | + | |
- | | + | |
- | | + | |
- | </ | + | |
- | ===== 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 | + | |
- | + | ||
- | * Hoher Speicherplatzbedarf - Jeder Aufruf benötigt Speicherplatz für lokale Variablen | + | |
- | * Unendliche Rekursion - Wenn man nicht aufpasst, enden die rekursiven niemals. | + | |
- | ===== Links ===== | + | |
- | + | ||
- | * [[https:// | + | |
- | * [[https:// | + |
schule/rekursion.txt · Zuletzt geändert: 2024-01-20 09:39 von pintman