inf-schule | Rekursion

Übungen

Aufgabe 1 - Summen von natürlichen Zahlen

In dieser Aufgabe geht es um die Berechnung von Summen von natürlichen Zahlen.

summe 5 = 1 + 2 + 3 + 4 + 5 = 15

Hinweis: In ähnlicher Form hast du solche Summen bereits im Abschnitt zum Begrüßungsproblem betrachtet.

(a) Im Rekursionsschritt reduziert man das Problem auf ein entsprechendes Problem in verkleinerter Form. Ergänze die Reduktionsregel am Zahlenbeispiel und in allgemeiner Form mit n.

summe 5 -> ... (summe 4)

(b) Im Rekursionsanfang gibt man die Lösung des Problems für einen Startwert direkt an. Vervollständige den Rukursionsanfang:

summe ? -> ...

(d) Optimiere die Implementierung mit Hilfe von Endrekursion.

Aufgabe 2 - exponentielles Wachstum

Schreibe eine Funktion, welche die Entwicklung eines Sparkontos rekursiv berechnet. Die Funktion soll sich folgendermaßen aufrufen lassen:

> depotstand 10000 5 2
11025 : Float

Überprüfe, ob deine Funktion endrekursiv ist. Falls nicht, optimiere sie entsprechend.

Aufgabe 3 - Fibonacci-Zahlen

Der Rechenmeister Fibonacci - der um 1200 in Pisa lebte - hat sich mit einer Zahlenfolge beschäftigt, die man mit einer Kaninchenvermehrung verdeutlichen kann:

Kaninchen sind in diesem Modell ab dem zweiten Lebensmonat geschlechtsreif und pflanzen sich fort. Es gilt also:

fibo 1 = 1
fibo 2 = 1
fibo 3 = 2
fibo 4 = 3
fibo 5 = 5
fibo 6 = 8

Beschreibe anhand der Grafik wie sich die Zahl der Kaninchenpaare in Abhängigkeit vom Monat vergrößert. Ergänze die rekursive Problemlösung:

fibo n = fibo ... + ...

(a) Implementiere die Funktion in Elm. Tipp: Es gibt nicht nur einen Basisfall.

(b) Beschreibe das Problem der Implementierung mit Hilfe eines Aufrufbaums.

Die Grundidee ist, dass man zwei Akkumulatoren nutzt und so die Folge iterativ - also von 1 bis n - , statt rekursiv von n bis 1 - berechnet. Der Aufrufstapel für fibo 6 verdeutlicht dies:

fibHelper 6 1 1
fibHelper 5 1 2
fibHelper 4 2 3
fibHelper 3 3 5
fibHelper 2 5 8
fibHelper 1 8 13 -> Ergebnis: 8

Aufgabe 4 - Strings wiederholen

Im Modul String gibt es die Funktion String.repeat, die eine Zeichenkette n mal wiederholt:

> String.repeat 5 "HI"
"HIHIHIHIHI" : String

Schreibe deine eigene (endrekursive) Implementierung.

Aufgabe 5 - filter

Du kennst von vorherigen Abschnitten die Funktion List.filter, die anhand einer Boolschen Funktion überprüft, ob Elemente einer Liste behalten werden sollen:

> List.filter (\a -> modBy 3 a == 0) (List.range 1 20)
[3,6,9,12,15,18]
    : List Int