Zweck der rekursiven Listenverarbeitung: Listen beliebiger Länge bearbeiten können.
Grundidee: Jede nicht leere Liste besteht aus einem ersten Element und einer Restliste. Bei der rekursiven Verarbeitung wird das erste Element bearbeitet und anschliessend die selbe Prozedur mit der Restliste durchgeführt, bis die Restliste den einfachsten möglichen Fall darstellt (meist die leere Liste) und abgebrochen werden kann. Der Name rekursiv kommt daher, dass ein rekursiver Befehl sich sich selbst immer wieder selbst ausführt (bis die Abbruchbedingung erfüllt ist). Achtung: Abbruchbedingung nicht vergessen und sie muss in jedem Fall erfüllt werden können, sonst kann Prolog theoretisch unendlich lang rechnen.
Grundschema:
berechne(Liste, Lösung):-
Liste = [Anfang|Rest],
bearbeite(Anfang)
berechne(Rest, Restlösung)
%Abbruchbedingung:
berechne(einfachsteListe, einfachsteLösung).
"bearbeite(Anfang)" haben wir unter anderem durch "map (Anfang, AlternativerAnfang)" ersetzt. (Das bewirkt, dass immer wenn das zu bearbeitende Element das erste Argument ist, durch das zweite Argument ersetzt wird)
In vielen Fällen ist das "bearbeite(Anfang)" gar nicht nötig, sondern es genügt die richtige Abbruchbedingung (Beispiel: Ist eine Variable Element einer Liste?):
%rekursive Klausel
member(Gesucht, [Anfang|Rest]):-
member(Gesucht, Rest).
%Abbruchbedingung:
member(Gesucht, [Gesucht|Rest])