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

See also mutual recursion.