Benutzer-Werkzeuge

Webseiten-Werkzeuge


schule:rekursion

Dies ist eine alte Version des Dokuments!


Rekursion

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.

loese(<Problem>):
   ...
   loese(<einfacheres Problem>)
   ...

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.

REKURSIVE_METHODE(<Problem>):
  if <das Problem ist leicht>:
    <löse das Problem>
  else:
    <mache das Problem leichter>
    REKURSIVE_METHODE(<leichteres Problem>)

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.

anzahl(liste):
  anzahl = 0
  for element in liste:
    anzahl = anzahl + 1
 
  return anzahl

Ein rekursiver Algorithmus würde das Problem wie folgt lösen:

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 ausgeben(liste) ausgegeben werden. Nutze ein rekursives Verfahren. Überlege zunächst, für welche Liste das Problem leicht lösbar ist.

>>> ausgeben([1,2,3])
1
2
3
>>> ausgeben([1])
1

Ü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?

>>> suche(1, [1,2,3])
True

>>> suche(2, [1,2,3])
True

>>> suche(3, [1,2,3])
True

>>> suche(4, [1,2,3])
False

Übung Filtern

Schreibe einen rekursiven Algorithmus, der alle geraden Zahlen aus einer Liste zurück gibt.

>>> gerade([1,2,3])
[2]

>>> gerade([1,2,3,4])
[4, 2]

>>> gerade([1,3,4])
[4]

>>> gerade([])
[]

Übung Streckenalgorithmus

In 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?

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

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 Spiel einmal selbst aus.

Ein möglicher Algorithmus, um das Problem zu lösen.

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)

Ein 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.

>>> 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]

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.
schule/rekursion.1485437181.txt.gz · Zuletzt geändert: 2017-04-19 08:39 (Externe Bearbeitung)