Leider gibt es Fälle, bei denen
unser allgemeines Suchschema
nicht unmittelbar auf eine iterative Lösung führt,
nämlich dann, wenn die Datenstruktur, in der wir suchen,
beim Entfernen des Einstiegselements in mehrere Teile zerfällt.
Ein Beispiel ist etwa das Suchen in einem
Wald oder auch in seinem
äquivalenten Binärbaum.
PROCEDURE lookup(k: keytype; b: btree; VAR p: btree);
BEGIN IF b = NIL THEN p := NIL;
ELSE lookup(k, b^.left, p);
IF p = NIL THEN lookup(k, b^.right, p);
END;
END lookup;
Der zweite Aufruf von lookup ist
rechtsrekursiv
und kann wie gewohnt entfernt werden, der erste aber nicht:
PROCEDURE lookup(k: keytype; b: btree; VAR p: btree);
VAR Zustand: (suchen, ja, nein);
BEGIN Zustand := suchen;
WHILE Zustand = suchen
DO IF b = NIL THEN p := NIL; Zustand := nein;
ELSE lookup(k, b^.left, p);
IF p <> NIL THEN Zustand := ja;
ELSE b := b^.right;
END;
END;
END;
END lookup;
Behelfen könnte man sich mit einer zusätzlichen
Liste der noch unerledigten Teilprobleme;
dies macht unser Übersetzer beim rekursiven Aufruf
aber ohnehin automatisch.