Grundkurs Common-Lisp WS 96|97

4. Übung (20-nov-1997)

Rekursion (2 + 3 = 5 Punkte)

a)

Schreibe eine rekursive Funktion sum(), die alle Zahlen in einer Liste (von Zahlen) summiert.

?

(sum '(1 2 3 4)) 10

?

(sum '()) 0

c)

Doppelrekusion: erweitere die Funktion sum() aus Aufgabe a) so, daß alle Zahlen einer beliebig geschachtelten Liste summiert werden.

?

(sum3 '(((1) 2) (3 4))) 10

Mehr Rekursion (3 + 3 + 3 = 9 Punkte)

Schreibe eine zweistellige rekursive Funktion vereinigung(), die aus zwei Mengen in Listendarstellung (jedes Element ist nur einmal enthalten; die Ordnung der Elemente ist irrelevant) die Vereinigungsmenge berechnet. Definiere analoge Funktionen schnitt() und differenz(), die die Schnitt- beziehungsweise Differenzmengenberechnung ausführen; e.g.\

? (vereinigung '(a b c) '(d e a))
(C B D E A)
? (schnitt '(a b c) '(d e a))
(A)
? (differenz '(a b c) '(d e a))
(B C)

Hinweis: Verwende in der Funktionsdefinition von differenz() die eingebaute Funtion remove(). Alle drei Funktionen können davon ausgehen, daß die Eingabelisten ordentliche Mengen sind.

Geheimnisvolle Rekursion (6 Punkte)

Beschreibe den Zweck der folgenden Funktion:

(defun elch (foo)
  (cond ((null foo) foo)
        ((atom foo) (list foo))
        (t (append (elch (first foo))
                   (elch (rest foo))))))

Wie genau funktioniert elch()? Gehe in der Beschreibung auf jeden der drei Zweige der Fallunterscheidung ein: warum sind sie nötig; was machen sie?

Schmökrekursion (3 rekursive Schmökpunkte)

Erweitere die Funktion sum3() aus Aufgabe 1 so, daß die Liste auch andere Elemente enthalten kann (die allerdings nicht summiert werden sollen).

?

(sum4 '(1 a b 3)) 4

?

(sum4 '(1 (eine liste mit (5) elemente) 2)) 8

?

(sum4 '((((diese) ko-) mische liste) enthaelt (keine ((zahlen))))) 0