;;; <Ariadne Tiefe.scm> (define (Tiefensuche Start Ziel Suchraum) (let t-s ((Alternativen (Nachfolger Start)) (besucht (list Start))) (cond ((null? Alternativen) #f) ; [Anm.1] ((member (car Alternativen) besucht) ; [Anm.2] (t-s (cdr Alternativen) besucht)) ((eq? (car Alternativen) Ziel) ; [Anm.3] (writeln (reverse (cons (car Alternativen) besucht))) #t) ((t-s ; [Anm.4]: (Nachfolger (car Alternativen) Suchraum) (cons (car Alternativen) besucht))) (else (t-s ; [Anm.5] (cdr Alternativen) besucht)))))
[Anm.1]: Wenn auf einer Rekursionstiefe alle Alternativen untersucht wurden, wird mit dem Wert "#f" zur aufrufenden Ebene zurueckgesprungen.
[Anm.2]: Wenn der aktuelle Knoten schon besucht wurde, wird versucht, mit dem naechsten Knoten der selben Ebene weiter zu arbeiten. Dies ist also der erste Fall in dem eine Alternative bearbeitet wird. (Es geht in die Breite. Aber: Nicht mit der Breitensuche verwechseln, s.u.)
[Anm.3]: Wenn das Ziel erreicht wurde, wird die Liste der besuchten Knoten in der richtigen Reihenfolge ausgegeben und es wird mit dem Wert "#t" zur aufrufenden Ebene zurueckgesprungen.
[Anm.4]: Hier erfolgt der eigentliche Abstieg in der Rekursion.
[Anm.5]: Wenn die Rekursion in der Tiefe erfolglos war, müssen noch die Alternativen versucht werden. ( siehe auch [Anm.2] )
Das Programm enthält noch eine zusätzlich anzumerkende Kleinigkeit. Es ist in Scheme zulässig, den Wert der Bedingung in einem cond als Wert der Auswertung zu verwenden. Daher kann in diesem Fall auf einen gesonderten Auswertungsteil verzichtet werden. Ist der Wert der Bedingung nicht #f, wird dieser einfach als Wert zurückgegeben.