The second clause is clearly recursive -
member(Item, [_|Rest]) :- member(Item, Rest).
memberoccurs both in the head and the body. A recursive procedure can work because of two things:
member) in the body is in some way simpler than that in the head, so that Prolog is being asked to solve a simpler problem. (In
member, the list that is the argument to
memberin the body is shorter by one than that in the head.)
member, the first clause is the trivial branch - it says that
Itemis the first member of the list that is the second argument.)
A recursive data structure is one where the structures
include substructures whose principle functor
is the same as that of the whole structure. For example, the tree
tree(tree(empty, fred, empty), john, tree(empty, mary, empty))
is recursive. Recursive data structures require recursive procedures to process them.
It can help, in understanding recursion, to separate
the different depths of recursive invocation
of Prolog rules by drawing boxes around the parts that correspond
to a particular invocation, and giving separate (but systematic)
names to the variables in each invocation. So if the rule involves
X, then in the first invocation, we refer
X1, while in the second (recursive)
invocation, we refer to the new
and so on.
Let's try this out with the recursive procedure
In each recursive call of
sumlist, there is a separate
instance of the variables
SumOfRest, and these are distinguished
by subscripts - so
First1 is the instance of
First in the top-level call of
First2 is the instance of
First in the
first recursive call to
% sumlist(NumList, SumOfList) - binds SumOfList to the sum % of the list NumList of numbers. % Rule 1: sumlist(, 0). % Rule 2: sumlist([First | Rest], Sum) :- sumlist(Rest, SumOfRest), % Goal 2.1 Sum is First + SumOfRest. % Goal 2.2and the query
?- sumlist([5, 2, 1], Answer).
Choose Rule: only rule 2 matches, with
Try doing a Prolog trace of the same query and procedure, and compare the results.
Here are some tips on writing recursive procedures in Prolog..
See also mutual recursion.