;;;
;;; (1) Rekursion
;;;

;;;
;;; add up a list of numbers; e.g. 
;;;   (sum '(1 2 3 4)) --> 10
;;;
(defun sum (list)
  (cond ((null list) 0)
        (t (+ (first list) (sum (rest list))))))

;;;
;;; add up a (possibly nested) list of numbers; 
;;;   e.g. (sum3 '(1 (2 (3) 4))) --> 10
;;;
(defun sum3 (list)
  (cond ((null list) 0)
        ((atom list) list)
        (t (+ (sum3 (first list)) (sum3 (rest list))))))

;;;
;;; (2) Mehr Rekursion
;;;

(defun vereinigung (menge-1 menge-2)
  (cond ((null menge-1) menge-2)
        ((member (first menge-1) menge-2)
         (vereinigung (rest menge-1) menge-2))
        (t (cons (first menge-1) (vereinigung (rest menge-1) menge-2)))))

(defun schnitt (menge-1 menge-2)
  (cond ((null menge-1) nil)
        ((member (first menge-1) menge-2)
         (cons (first menge-1) (schnitt (rest menge-1) menge-2)))
        (t (schnitt (rest menge-1) menge-2))))

(defun differenz (menge-1 menge-2)
  (cond ((null menge-1) nil)
        ((member (first menge-1) menge-2)
         (differenz (rest menge-1) menge-2))
        (t (cons (first menge-1) (differenz (rest menge-1) menge-2)))))

;;;
;;; (3) Geheimnisvolle Rekursion
;;;

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

;;; Die Funktion elch() nimmt ein Argument vom Typ Liste (Parameter .foo.).
;;; Die uebergebene Liste wird durch kombinierte Tiefen- und Breitensuche
;;; mittels doppelter Rekursion verflacht (i.e. es werden alle eingebetteten
;;; Atome auszer `nil' in einer flachen Liste aufgesammelt und zurueckgegeben).
;;; Beispiele:
;;;
;;;   (elch '(1 2 3 4))
;;;   --> (1 2 3 4)
;;;   (elch '(1 (2 (3) 4)))
;;;   --> (1 2 3 4)
;;;   (elch '(nil (nil (nil) nil)))
;;;   --> nil
;;;
;;; Die drei Zweige der Fallunterscheidungen kodieren die Abbruchbedingungen
;;; (Basisfaelle) und den doppelten rekursiven Aufruf; im einzelnen:
;;;
;;;   - (null foo) ist die Terminierungsbedingung der Breitensuche (i.e. des
;;;     Teils des rekursiven Aufrufs, der die Eingabeliste elementweise von
;;;     links nach rechts traversiert) und wird erfuellt, sobald das Ende der
;;;     uebergebenen Liste erreicht ist;
;;;   - (atom foo) ist die Terminierungsbedingung der Tiefensuche (i.e. des
;;;     Teils des rekursiven Aufrufs, der fuer jedes Listenelement eine Ebene
;;;     absteigt) und wird erfuellt, sobald ein Element nicht mehr listenwertig
;;;     ist, so dasz nicht weiter in die Tiefe abgestiegen werden kann;
;;;   - der dritte zweig wird als default ausgefuehrt, wenn keine der beiden
;;;     Abbruchbedingungen erfuellt ist; durch doppelten rekursiven Aufruf
;;;     ueber dem (aktuell) ersten Element und der Restliste nach Abtrennen des
;;;     ersten Elements entstehen fuer jeden Aufruf von elch() zwei neue
;;;     Aufrufe, die je einen Schritt weiter in die Tiefe (auf (first foo)) und
;;;     Breite (ueber (rest foo)) suchen.

;;;
;;; (4) Schmökrekursion
;;;

;;; um sum3() robust bezueglich Listenelementen zu machen, die keine Zahlen
;;; (und insofern nicht summierbar sind), musz ein weiterer Zweig in die
;;; Fallunterscheidung genommen werden, der beim Abbruch der Tiefensuche
;;; (i.e. wenn die Eingabe keine Liste mehr ist) nach dem Datentyp des Objektes
;;; unterscheidet: Zahlen werden fuer die Addition unveraendert zurueckgegeben;
;;; fuer alle anderen Atome liefert sum4() das neutrale Element der Addition
;;; (die 0).

(defun sum4 (list)
  (cond ((null list) 0)
        ((numberp list) list)
        ((atom list) 0)
        (t (+ (sum4 (first list)) (sum4 (rest list))))))