i

Strukturierung: Rekursive Funktionsaufrufe

Rekursion in Racket

Da rein funktionale Sprachen keine Schleifenstrukturen wie while oder for unterstützen, ist die Rekursion hier besonders wichtig, da diese eine Möglichkeit für Iterationen bietet. Rekursion ist jedoch auch in vielen anderen Fällen nützlich, da durch Rekursion Probleme in kleinere, lösbare Teilprobleme zerlegt werden können.

Rekursion ist eine Problemlösestrategie, in der sich eine Funktion selbst aufruft. Diesen Aufruf nennen wir einen Rekursionsschritt. Durch jeden Rekursionsschritt wird das Problem auf ein kleineres, strukturgleiches Teilproblem heruntergebrochen, bis ein Basisfall erreicht wird, für welchen das Problem direkt lösbar ist. Das Erreichen des Basisfalls löst das Gesamtproblem entweder direkt oder es kann anschließend schrittweise durch Nutzung der Teillösung gelöst werden.
Betrachten wir beispielhaft die Funktion select-index für die Selektion eines Listenelements:
  • Wir wissen, dass wir mit first das erste Element einer Liste in Racket erhalten. Unser Basisfall stellt damit den Fall dar, dass unser gesuchtes Element genau auf Index 0 liegt.
  • Ist ersteres nicht der Fall, können wir durch einen Reduktionsschritt das Problem auf die Betrachtung einer gekürzten Liste ohne das vorherige erste Element herunterbrechen.
  • Wir wiederholen den Reduktionsschritt nun so lange, bis wir den Basisfall erreicht haben, in welchem das gesuchte Element auf Index 0 liegt.
(: select-index ((list-of any) natural -> any))
(check-expect (select-index (list 10 20 30) 2) 30)

(define select-index
  (lambda (l i)
    (cond
     ([= i 0] (first l))
     (else (select-index (rest l) (- i 1))))))
(Hinweis: die Funktion fängt zur besseren Übersichtlichkeit keine unzulässigen Indizes ab)

Aufgabe 1: Gehaltsanalyse auf einer unsortierten Liste

Bestehende Datei - rekursion.rkt

Zur Gehaltsanalyse legt auch Firma-B eine Liste mit den Jahresgehältern aller 80 Mitarbeitenden vor:

(define firmaB
  (list 6680 48000 55000 34000  6680 60000 42000 6680 42000 55000 6680 48000 55000 6680 42000 60000 70000 48000 34000 34000 6680
        48000 42000 55000 34000 42000 42000 42000 60000 48000 55000 48000 48000 55000 48000 77000 48000 55000 60000 48000 42000
        34000 55000 55000 6680 6680 48000 6680 55000 90000 34000 48000 55000 42000 70000 55000 48000 6680 42000 90000 48000
        34000 48000 6680 55000 42000 42000 34000 60000 55000 42000 48000 115000 42000 55000 55000 48000 55000 48000 42000))

(a) Bestimme die ersten 7 Elemente sowie den Medianwert der Liste firmaB. Beurteile, wie aussagekräftig die erhaltenen Daten sind.

(b) Schreibe eine Sortierfunktion, die Zahlenlisten aufsteigend ordnet.
Benutze als Sortieralgorithmus entweder Insertion Sort oder Merge Sort.

Insertion Sort:
Mit Insertion Sort sortieren wir eine Liste, indem wir ein neues Element an die richtige Stelle in eine vorsortierte Liste einfügen. Schematisch haben wir zu Beginn einer Sortierung eine leere Liste und eine unsortierte Liste. Wir füllen die leere Liste, indem wir immer das erste Element der unsortierten Liste an die richtige stelle der neuen (anfänglich leeren) Liste einfügen. Im nächsten Schritt betrachten wir den Rest der unsortierten Liste.
$empty \leftarrow (list\ 1\ 0\ \text{-}4\ 2\ 7\ 6)$
$(list\ 1) \leftarrow (list\ 0\ \text{-}4\ 2\ 7\ 6)$
$(list\ 0\ 1) \leftarrow (list\ \text{-}4\ 2\ 7\ 6)$
$(list\ \text{-}4\ 0\ 1) \leftarrow (list\ 2\ 7\ 6)$
$(list\ \text{-}4\ 0\ 1\ 2) \leftarrow (list\ 7\ 6)$
$(list\ \text{-}4\ 0\ 1\ 2\ 7) \leftarrow (list\ 6)$
$(list\ \text{-}4\ 0\ 1\ 2\ 6\ 7)$

Insertion Sort Laufzeit
Average-Case $O(n^2)$
Best-Case $O(n)$
Worst-Case $O(n^2)$

Merge Sort:
Der Algorithmus für Merge Sort ist zwar etwas komplizierter zu implementieren als der von Insertion Sort, dafür ist der Algorithmus aber auch durchschnittlich effizienter. Merge Sort arbeitet nach dem Prinzip Teile und Herrsche. Der Algorithmus ist dabei in zwei Phasen unterteilt: eine Split‑Phase und eine Merge‑Phase.

In der Split‑Phase wird die Liste solange in zwei (möglichst gleich große) Teile zerlegt, bis nur noch Listen mit einem Element übrig sind. In der Merge‑Phase werden diese einzelnen Elemente nun paarweise sortiert wieder zusammengefügt. Im Sortierprozess der Merge‑Phase werden immer zwei Listen miteinander verglichen. Dabei wird immer das erste Element der Listen verglichen. Das kleinste der beiden Elemente wird zu einer neuen sortierten Liste angefügt. Im nächsten Vergleichsprozess betrachten wir den Rest der unsortierten Liste, aus der das vorherig kleinste Element stammt.

Schematischer Ablauf von Merge Sort:
Merge Sort


Beispielhafter Vergleichsprozess zweier Listen: $(list\ 2\ 7)$ und $(list\ \text{-}1\ 6)$

  1. Vergleiche $2$ und $\text{-}1$
    $empty \leftarrow (list\ 2\ 7)\ (list\ \text{-}1\ 6)$
  2. Vergleiche $2$ und $6$
    $(list\ \text{-}1) \leftarrow (list\ 2\ 7)\ (list\ 6)$
  3. Vergleiche $7$ und $6$
    $(list\ \text{-}1\ 2) \leftarrow (list\ 7)\ (list\ 6)$
  4. Füge $7$ an - da kein weiteres Element zum Vergleichen mehr vorhanden ist
    $(list\ \text{-}1\ 2\ 6) \leftarrow (list\ 7)\ empty$
    $(list\ \text{-}1\ 2\ 6\ 7)$

Merge Sort Laufzeit
Average-Case $O(n \cdot log(n))$
Best-Case $O(n \cdot log(n))$
Worst-Case $O(n \cdot log(n))$

(c) Bestimme die vier höchsten und zwölf geringsten Jahresgehälter in Firma-B.

(d) Vergleiche Firma-A und Firma-B. Welche der Firmen hat ein höheres Median-Gehalt, welche den höheren Mittelwert?

(e) Firma-B beschäftigt mehrere Angestellte auf Minijob-Basis (Stand 2025: die Personen, deren Jahresgehalt 6680 € beträgt). Rechne sämtliche Minijob-Angestellten der Firma-B heraus und vergleiche die Firmen wie in (c) beschrieben anschließend erneut.

Suche

v
100.137.4.1.1.2 Strukturierung: Rekursive Funktionsaufrufe
Kopieren durch Anklicken

Rückmeldung geben