recursion
A recursive rule is one which refers to itself. That is, its body includes a goal which is an instance of the relation that appears in the head of the rule. A well-known example is the `member` procedure:
`member(Item, [Item|Rest]).`
`member(Item, [_|Rest]) :- member(Item, Rest).`
The second clause is clearly recursive - `member` occurs both in the head and the body. A recursive procedure can work because of two things:
1. the instance of the relation (like `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 `member` in the body is shorter by one than that in the head.)
2. there must be a "trivial branch" "base case" or "boundary case" to the recursion - that is, a clause that does not involve recursion. (In the case of `member`, the first clause is the trivial branch - it says that `member` succeeds if `Item` is 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 structure:
`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 a variable `X`, then in the first invocation, we refer to `X` as `X1`, while in the second (recursive) invocation, we refer to the new `X` as `X2`, and so on.

Let's try this out with the recursive procedure `sumlist`. In each recursive call of `sumlist`, there is a separate instance of the variables `First`, `Rest`, `Sum`, and `SumOfRest`, and these are distinguished by subscripts - so `First1` is the instance of `First` in the top-level call of `sumlist`, and `First2` is the instance of `First` in the first recursive call to `sumlist`.

```% 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.2
```
and the query
`?- sumlist([5, 2, 1], Answer).`

`sumlist[5, 2, 1], Answer).`
Choose Rule: only rule 2 matches, with
`First1 = 5; Rest1 = [2, 1]; Sum1 = Answer`
Goal 2.1: `sumlist(Rest1, SumOfRest1),`
`sumlist([2, 1], SumOfRest1),`
Choose Rule: only rule 2 matches, with
`First2 = 2; Rest2 = [1]; Sum2 = SumOfRest1`
Goal 2.1: `sumlist(Rest2, SumOfRest2),`
`sumlist([1], SumOfRest2),`
Choose Rule: only rule 2 matches, with
`First3 = 1; Rest3 = []; Sum3 = SumOfRest2`
Goal 2.1: `sumlist(Rest3, SumOfRest3),`
 `sumlist([], SumOfRest3),` Choose Rule: only rule 1 matches, with `0 = SumOfRest3` `∴ SumOfRest3 = 0`
Goal 2.2: ```Sum3 is First3 + SumOfRest3. = 1 + 0 = 1 ∴ SumOfRest2 = Sum3 = 1```
Goal 2.2: ```Sum2 is First2 + SumOfRest2. = 2 + 1 = 3 ∴ SumOfRest1 = Sum2 = 3```
Goal 2.2: ```Sum1 is First1 + SumOfRest1. = 5 + 3 = 8 ∴ Answer = Sum1 = 8```

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..