Racket Rekursion meistern: Csci 301 Lab 2 Tutorial (gen-list, sum, pair-sum?)

Einführung: Rekursion in Racket – mehr als nur ein Lab

Rekursion ist das Herzstück der funktionalen Programmierung. In diesem Tutorial begleiten wir dich durch die zentralen Konzepte, die im Csci 301 Lab 2 behandelt werden. Du wirst nicht nur die berühmte mystery-Funktion verstehen, sondern auch lernen, wie du mit dem DrRacket-Debugger Schritt für Schritt durch deinen Code gehst. Am Ende wirst du eigene rekursive Funktionen schreiben können – von gen-list bis pair-sum?. Alles basierend auf aktuellen Beispielen, die dir zeigen, wie Rekursion auch in der echten Welt (z. B. bei Algorithmen für Social-Media-Feeds oder KI-gestützten Empfehlungen) eingesetzt wird.

1. Die mystery-Funktion entschlüsseln

Die Funktion mystery ist ein klassisches Beispiel für Rekursion auf Listen. Hier ist der Code:

(define (mystery L)
  (if (null? L)
      L
      (append (mystery (cdr L)) (list (car L)))))

Wenn du diese Funktion aufrufst, zum Beispiel mit (mystery '(1 2 3)), erhältst du (3 2 1). Sie kehrt also die Liste um. Aber wie funktioniert das?
Die Logik: Ist die Liste leer, gib sie zurück. Sonst: Rekuriere auf dem Rest (cdr) und hänge das erste Element (car) als neue Liste hinten an. Das ist die Standardmethode, um eine Liste umzukehren – allerdings ineffizient, weil append jedes Mal die ganze Liste kopiert. In der Praxis (z. B. beim Verarbeiten von Datenströmen in KI-Apps) würde man eine effizientere Methode wie reverse oder Akkumulator-Rekursion verwenden.

Frage 1: Was macht mystery?
Antwort: Sie kehrt die Liste um.

Frage 2: Wie wird der Rückgabewert bestimmt?
Antwort: In Racket ist der letzte ausgewertete Ausdruck der Rückgabewert. Hier: Wenn die Liste leer ist, wird L (also '()) zurückgegeben. Sonst wird das Ergebnis von append zurückgegeben. Es gibt kein explizites return – die letzte Expression ist der Rückgabewert.

2. Debugging mit DrRacket – Schritt für Schritt

Um die Rekursion live zu sehen, klicke auf „Debug“ und dann auf „Step“. Du siehst einen grünen Pfeil, der die aktuelle Auswertung anzeigt, und einen roten Kreis für Breakpoints. Hover über L zeigt den aktuellen Wert. Das ist extrem hilfreich, um zu verstehen, wie Rekursion arbeitet – ähnlich wie wenn man in einer modernen KI-Entwicklungsumgebung den Datenfluss verfolgt.

3. Die erweiterte mystery-Funktion mit displayln

(define (mystery L)
  (if (null? L)
      L
      (begin (displayln L)
             (append (mystery (cdr L)) (list (car L))))))

Was macht begin? Es fasst mehrere Ausdrücke zusammen und gibt den Wert des letzten zurück. Nützlich für Seiteneffekte wie Ausgabe.
Was macht displayln? Es gibt den Wert auf der Konsole aus (Seiteneffekt) und gibt #<void> zurück. So siehst du, wie die Liste bei jedem Aufruf schrumpft – perfekt zum Lernen.

4. Eigene rekursive Funktionen schreiben

gen-list: Eine Liste von Zahlen erzeugen

(define (gen-list start end)
  (if (> start end)
      '()
      (cons start (gen-list (+ start 1) end))))

Diese Funktion erzeugt eine Liste aufeinanderfolgender Ganzzahlen. Wenn start > end, gib die leere Liste zurück. Sonst füge start an den Anfang der rekursiv erzeugten Liste von start+1 bis end. Das ist wie das Generieren von Indexbereichen in Schleifen – nur rekursiv.

sum: Summe aller Elemente einer Liste

(define (sum lst)
  (if (null? lst)
      0
      (+ (car lst) (sum (cdr lst)))))

Leere Liste → Summe 0. Sonst: erstes Element plus Summe des Rests. Einfach und elegant. In der Praxis nutzt man oft apply + oder foldl, aber Rekursion ist die Grundlage.

retrieve-first-n: Die ersten n Elemente extrahieren

(define (retrieve-first-n n lst)
  (cond
    [(or (<= n 0) (null? lst)) '()]
    [else (cons (car lst) (retrieve-first-n (- n 1) (cdr lst)))]))

Wenn n <= 0 oder die Liste leer ist, gib die leere Liste zurück. Sonst nimm das erste Element und rufe rekursiv mit n-1 und dem Rest auf. Das ist analog zu „Top-N“-Empfehlungen in Streaming-Diensten – nur rekursiv implementiert.

pair-sum?: Prüfen, ob zwei benachbarte Elemente eine bestimmte Summe ergeben

(define (pair-sum? lst val)
  (cond
    [(or (null? lst) (null? (cdr lst))) #f]
    [(= (+ (car lst) (cadr lst)) val) #t]
    [else (pair-sum? (cdr lst) val)]))

Die Funktion prüft, ob zwei benachbarte Werte in der Liste zusammen val ergeben. Wenn die Liste weniger als zwei Elemente hat: #f. Sonst: Wenn die Summe von erstem und zweitem Element gleich val ist, #t. Sonst: Rekursion auf dem Rest (cdr). Das ist nützlich für die Analyse von Datenreihen, z. B. in der Finanzwelt, wo man nach aufeinanderfolgenden Tagen sucht, deren Kurse eine bestimmte Summe ergeben.

Fazit: Rekursion als mächtiges Werkzeug

Rekursion in Racket ist nicht nur eine akademische Übung – sie ist die Grundlage vieler Algorithmen, die in KI, Datenanalyse und App-Entwicklung verwendet werden. Mit dem DrRacket-Debugger kannst du jeden Schritt nachvollziehen. Übe die Funktionen aus diesem Lab, und du wirst ein tieferes Verständnis für funktionale Programmierung entwickeln. Viel Erfolg!