Iteration vs. Rekursion


Iteration

Unter einer Iteration (von lat. iterare "wiederholen") versteht man in der Mathematik / Informatik eine Methode sich der Lösung eines Problems schrittweise, aber zielgerichtet anzunähern.

Daher findet man oft auch den Begriff "Näherungsverfahren". Die Methode der Iteration besteht in der wiederholten Anwendung ein und desselben Rechenverfahrens. Dabei wird das Ergebnis eines Iterationsschrittes als Ausgangswert des jeweils nächsten Schrittes genommen (siehe Abbildung). Dieses Verfahren wird solange wiederholt bis eine gewünschte Abbruchgenauigkeit (oft so genannte Maschinengenauigkeit eps) erreicht wird.

Prinzip der Iteration

Iterative Verfahren werden zur Problemlösung vor allem aus zwei Gründen eingesetzt:

  1. Für das zu lösende Problem existiert keine explizite Lösung.
  2. Es existiert zwar eine explizite Lösung, diese ist aber nur mit hohem Aufwand zu berechnen. Eine iterativ berechnete Lösung lässt sich schneller und mit weniger Aufwand angeben.
Aufgabe

Man kann die Fakultät n! einer natürlichen Zahl n iterativ berechnen, indem man zunächst 1 mit 2 multipliziert, dann dieses Ergebnis mit 3, dieses Ergebnis dann mit 4 usw., bis man schließlich n erreicht hat.


Rekursion

Manche Probleme lassen sich dadurch lösen, dass man sie auf eine einfachere Version ihrer selbst zurückführt. Dies bedeutet, dass man das Problem so lange auf sich selbst zurückführt, bis es sich einfach lösen lässt. Ein solches Verfahren nennt man Rekursion (von lat. recurrere "zurücklaufen").

Ein besonders schönes und auch anschauliches Beispiel für dieses Prinzip ist die bekannte russische Holzpuppe Matrjoschka.

Matrjoschka

Script: rekursion.pdf

Die Rekursion stellt ein sehr elegantes Verfahren zur Lösung komplizierter Probleme dar. Allerdings ist der benötigte Rechenaufwand sehr hoch, da die rekursive Funktion mehrfach hintereinander aufgerufen wird. Das Zwischenergebnis muss dabei immer auf einem Stack (Stapelspeicher) abgelegt werden. Dadurch ergibt sich ein hoher Speicherbedarf, der u.U. zu einem Stapelüberlauf (stack overflow) und damit zu einem Programmabsturz führen kann.

Aufgaben
  1. Schreiben Sie ein Programm zur rekursiven Berechnung der Fakultät einer natürlichen Zahl n! Orientieren Sie sich dabei an den Hinweisen im Script!

    Musterlösung zur Berechnung der Fakultät (sowohl iterativ wie auch rekursiv): fakultaet.zip

  2. Berechnen Sie die Summe der ersten n natürlichen Zahlen s(n) = 0 + 1 + 2 + 3 + ... + n rekursiv. Orientieren Sie sich dabei an dem rekursiven Ansatz der Fakultätsfunktion!
  3. Berechnen Sie die Summe der ersten n Quadratzahlen q_summe(n) = 12 + 22 + ... + n2 mit Hilfe einer rekursiven Funktion!

    Musterlösung der Aufgaben zur Rekursion: bsp_rekursion.zip

  4. Von Leonardo Pisano (ca. 1170 bis 1230), auch Fibonacci genannt, stammt folgende Aufgabe: In einer von Kaninchen freien Gegend wird ein frisch geborenes Pärchen Kaninchen ausgesetzt. Nach einem Monat ist es geschlechtsreif. Nach zwei Monaten bringe dieses Pärchen wieder ein Pärchen zur Welt. Nach drei Monaten sind dann drei Pärchen vorhanden: Das zuerst ausgesetzte hat wieder ein Pärchen geboren, während das zum Zeitpunkt 2 (Monate) geborene Pärchen geschlechtsreif geworden ist. Da kein Pärchen sterben soll, sind also nach vier Monaten 5 Pärchen vorhanden (siehe Abbildung).

    Vermehrung von Kaninchen

    n (Monate) 0 1 2 3 4 5 6 7 8 9
    Anzahl der Pärchen 1 1 2 3 5 8 ? ? ? ?

    1. Füllen Sie die Tabelle vollständig aus!
    2. Bestätigen Sie mithilfe Ihrer ausgefüllten Tabelle, dass für die Bildungsvorschrift der Fibonacci-Folge gilt:

      Fibonacci-Folge

      Dabei ist A(n) die Anzahl der Pärchen von Kaninchen in n Monaten. Das Besondere an diesem Beispiel ist, dass innerhalb des Rekursionsschrittes die rekursive Funktion mehrfach (hier bei der Fibonacci-Folge genau zwei mal) aufgerufen wird. Dadurch vervielfachen sich die rekursiven Aufrufe mit zunehmender Tiefe. Dies lässt sich sehr gut mit einer Baumstruktur darstellen. Man spricht dehalb in diesem Zusammenhang von einer Baumrekursion.

    3. Schreiben Sie ein Programm, das nach Eingabe von n den Bestand an Kaninchenpaaren ausgibt!
    4. Schreiben Sie ein Programm, das nach Eingabe einer Kaninchenzahl (in Pärchen) ausgibt, wann diese Zahl erreicht oder überschritten ist!
    5. entnommen aus: Junger u.a.: Informatik, Diesterweg/Sauerländer, 1988

      Musterlösung: fibonacci.zip


zuletzt geändert am:
Eine Seite von Mirko Hans