/home/bakera/wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Zuletzt angesehen:
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 [2017-01-12 11:12] – [Allgemeiner Aufbau] marco.bakeraschule:rekursion [2024-01-20 08: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> +
-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> +
-anzahl(liste): +
-  if liste ist leer: +
-    return 0 +
- +
-  else: +
-    liste_kleiner = liste.entferneErstesElement() +
-    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 Algorithmus in dem VisualStudio-Projekt entsprechend. +
- +
-===== Ü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> +
-===== 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. +
-===== 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.1484219572.txt.gz · Zuletzt geändert: (Externe Bearbeitung)