Wie das Prinzip arbeitet, sehen wir etwa an einem
schon früher angesprochenen Beispiel:
Kopieren einer linear verketteten Liste.
An der unmittelbar naheliegenden rekursive Version
Hinter der gezeigten Reduktion einer
rechtsrekursiven Problemlösung auf eine iterative Version
steht die Idee, den Aktivierungsblock
der ersten Inkarnation der Prozedur
wiederzuverwenden , statt für die rekursiv aufgerufene
Instanz ein neues Exemplar anzulegen.
Dies ist möglich, weil sein Inhalt hier nach der Rückkehr
aus dem rekursiven Aufruf nicht mehr benötigt wird
bis auf die Rückkehr-Information
und den Ergebnisverweis,
die beide noch richtig stehen;
das rekursiv gerufene (bzw. hier direkt aktivierte!) Exemplar
benötigt nur neue Eingangsparameterwerte,
und die haben wir selbst korrekt umbesetzt.
Wie das Prinzip arbeitet, sehen wir etwa an einem
schon früher angesprochenen Beispiel:
Kopieren einer linear verketteten Liste.
An der unmittelbar naheliegenden rekursive Version
PROCEDURE copy(l: liste; VAR p: liste):
BEGIN IF l <> NIL
THEN NEW(p);
p^.wert := l^.wert; copy(l^.tail, p^.tail);
ELSE p := NIL;
END;
END copy;
stört uns, daß sich der Ergebnisparameter p
beim rekursiven Aufruf auf ein anderes Objekt als beim Erstaufruf bezieht.
Wir verwenden für das Kopieren des Listenschwanzes
nun eine neue Routine copytail,
der wir den Bezug auf den bereits existierenden
Kopf der neuen Liste als Wertparameter mitgeben,
und die nur den Schwanz der Liste kopieren soll:
PROCEDURE copy(l: liste; VAR p: liste):
BEGIN IF l <> NIL
THEN NEW(p);
p^.wert := l^.wert; copytail(l, p);
ELSE p := NIL;
END;
END copy;
Die Routine copytail wird nun nicht mehr
mit einer leeren Liste aufgerufen; der Sonderfall ist nun,
daß die Liste nur aus dem Kopf besteht.