Der Befehl cond ermöglicht unter Scheme eine Mehrfachverzweigung. Die einzelnen Zweige werden durch sequentielle Abarbeitung der Bedingungen erreicht. Dabei wird nach einem Erfolgsfall nicht mehr überprüft, ob noch weitere zutreffende Bedingungen vorhanden sind, sondern nur der Auswertungsteil der ersten zutreffenden Bedingung bearbeitet und danach der cond - Befehl mit dem Wert dieses Auswertungsteils verlassen.
Grundsätzlich folgen auf cond daher stets mehrere Paare von ...
Am Schluss sollte immer die "Bedingung" else oder statt dessen #t mit einem Auswertungsteil folgen, von dem der Wert bestimmt wird, wenn keine der vorherigen Bedingungen zutraf.
Im vorgegebenen Fall wird also in allen Fällen zunächst mit...
...untersucht, ob die Liste der Alternativen leer ist. Da dies bedeutet, dass auf dieser Stufe alle möglichen Alternativen untersucht wurden, wird ein backtracking ausgelöst. Dabei wird der Funktionswert #f zurückgegeben, um der aufrufenden Stelle den Misserfolg mitzuteilen.
Nur wenn die o.a. Bedingung nicht erfüllt war, also noch Alternativen zur Verfügung stehen, wird die zweite Bedingung geprüft, die in diesem Beispiel...
...lautet. Der Bedingungsteil ist wieder in der ersten Klammer zu finden, er überprüft, ob mit dem ersten Element der Alternativen das Ziel erreicht wurde. Bemerkenswert ist noch das Nachfolgen von zwei weiteren Ausdrücken. Der Auswertungsteil kann also aus einer Sequenz mehrerer Ausdrücke bestehen, ohne dass er noch gesondert geklammert werden muss. Hier wird zunächst als Nebeneffekt der aktuelle Knoten ausgegeben (z.B. Bildschirmdarstellung) und dann als Wert zurückgegeben.
In der nachfolgenden Abfrage...
...wird dieser Erfolgsfall auf den vorigen Suchstufen verarbeitet. Hierhin gelangt das Programm nur, wenn auf dieser Stufe weder die Alternativen leer waren noch das Ziel erreicht wurde.
An dieser Stelle führt das Programm den eigentlichen Schritt in die Tiefe aus. Es ruft sich rekursiv selbst auf und übergibt dabei als Parameter die von der Hilfsfunktion Nachfolger bestimmten Alternativen, die auf den aktuellen Knoten folgen können. Da das Programm so konstruiert ist, dass es selbst wie eine Bedingung arbeitet -im Misserfolgsfall wird (s.o.) #f zurückgegeben, kann sein Aufruf an Stelle einer Bedingung stehen. Seine textliche Darstellung könnte lauten: "Wenn du auf der nächsten Stufe keinen Misserfolg feststellst, dann ... "
Wird also von der nächsten Stufe -eigentlich müsste es nun #t heißen- richtig ist aber etwas anderes als #f, denn das wird in einer Bedingung von Scheme stets wie #t interpretiert, dann befinden wir uns auf einem Erfolgspfad und es muss auch hier der aktuelle Knoten ausgegeben und als Wert zurückgegeben werden.
Wenn nun alle diese drei Fälle nicht zutrafen...
...muss in jedem Fall geklärt werden, was dann zu tun ist. Hier etwas sehr wichtiges: Das Programm muss die Alternativen abbauen! Dazu ruft es sich mit der Restliste der Alternativen selbst auf. Das geschieht wieder rekursiv, allerdings in diesem Fall nicht normal rekursiv, sondern endrekursiv. Dieser Unterschied ist für Scheme sehr wichtig: Es wird hier kein Aufruf auf dem Stack hinterlassen, der neue ersetzt einfach den letzten!