Tutorien für Algorithmen und Datenstrukturen 2

Übungsblatt 3: Rekursion und Iteration

Aufgabe 3-1

Folgende Teilaufgaben beziehen sich auf Ihre Lösung der Aufgabe 1-2.

1. Ändern Sie Ihre Summierungs-Methode derart, dass statt einer for-Schleife eine while-Schleife benutzt wird.
2. Ändern Sie Ihre Methode derart, dass statt einer Iteration eine Rekursion stattfindet.
3. Schreiben Sie eine weitere Methode, die statt der Summe die alternierende Summe errechnet. Die alternierende Summe des Arrays array sei definiert als:
   array[0] - array[1] + array[2] - array[3] + array[4] - …

Aufgabe 3-2

Die mathematische Fakultät ist definiert als n! := n · (n − 1)! ∀ n ∈ ℕ ∖ 0 mit 0! = 1.

Entwerfen Sie einen Algorithmus, der eine beliebige Fakultät rekursiv errechnet. Implementieren Sie diesen Algorithmus als Java-Methode, welche die Zahl n als Parameter übergeben bekommt und die Fakultät der Zahl n als Rückgabewert hat.

Aufgabe 3-3

Auf einer Party sind schon siebzehn der geladenen Gäste eingetroffen, Uwe ist der achtzehnte Gast. Alle Anwesenden stoßen mit jedem neuen Gast zur Begrüßung an. Nachdem auch er so begrüßt wurde, wird Uwe gefragt, wie oft die Gläser jetzt am Abend insgesamt erklungen sind. „Die Frage kann ich leicht beantworten,“ sagt Uwe, „wenn derjenige, der vor mir gekommen ist, dieses Problem für sich schon gelöst hat und mir sein Ergebnis nennt.“

Schreiben Sie eine rekursive Java-Methode für Uwe, mit der er in Zukunft durch Angabe der Anzahl der anwesenden Gäste (einschließlich ihm) diese Fragestellung beantworten kann.

Aufgabe 3-4

Begründen Sie, warum die rekursive Lösung eines Problems besser oder schlechter als die iterative Lösung sein könnte.

Zusatzaufgabe 3-5

Ändern Sie Ihre Lösung zu Aufgabe 3-2 derart, dass sie mit beliebig großen Zahlen korrekt funktioniert.

$Id: HEADER.html,v 1.5 2007/12/04 22:44:27 arne Exp $