Another classical example of recursion is the predicate append/3.
This predicate's three arguments are all lists. append(X, Y, Z) is
true if the Z is a list that is the result of sticking the list
Y onto the end of the list X. For example, append([a,b],
[c, d], [a,b,c,d]) is true.
The definition of append/3 is
similar to that of member/2 in that both involve working down a list
item by item. In the case of append/3, however, no test is being
carried out, and eventually the end of one of the lists will be reached,
leaving the empty list. This gives the base: what is the result of appending an
empty list to a list L? Clearly just L. In Prolog:
append([ ], List, List).
What if the first list isn't empty? We need to take its head, save it, and
stick it onto the front of the result. The result itself comes about as the
consequence of carrying out the same procedures on the tail of the list. This
is the recursive clause:
append([Head|Tail], List, [Head|Result]):- append(Tail, List, Result).
append/3
can also be used to generate solutions. Here are some examples:
a. last
argument a variable
| ?- append([a,b], [c,d], X). X = [a,b,c,d] ? yes
b. first argument a variable
| ?- append(X, [c,d], [a,b,c,d]). X = [a,b] ? yes
c. second argument a variable
| ?- append([a,b], X, [a,b,c,d]). X = [c,d] ? yes
d. first two arguments variables (and multiple solutions requested)
| ?- append(X, Y, [a,b,c,d]). X = [ ], Y = [a,b,c,d] ? ; X = [a], Y = [b,c,d] ? ; X = [a,b], Y = [c,d] ? ; X = [a,b,c], Y = [d] ? ; X = [a,b,c,d], Y = [ ] ? ; no