How does backtracking in recursion not cause an infinite loop?

The rules you stated are:

1. member(X, [X | R]).

The pipe operator separates the first element of the list from the rest of the list. So, if list is [1, 2, 3], X = 1, and R = [2, 3]. X is the car of the [X | R] list (i.e. first member).

So in this case, member(1, [1, 2, 3]). is true.

2. member(X, [Y | R]) :- member(X, R).

This second case covers when the first member of the list is different from X. If this is so, member(X , R) is called and this inspects the cdr of the list (i.e. from second element on).

So, member(1, [1, 2, 3]). doesn't trigger a recursion.

What happens, for instance, when the element is not on the list ?

For brevity, member(1, [2]). is true or false ?

This falls on the second rule, since X = 1 is different from Y = 2.

But then, the cdr of the list is an empty list (i.e. there are no elements beside the first).

So member(1, [2]) :- member(1, [])., and this member(1, []) evaluation is always false.

Prolog's output:

~ $ swipl
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
Please run ?- license. for legal details.

For online help and background, visit http://www.swi-prolog.org
For built-in help, use ?- help(Topic). or ?- apropos(Word).

?- [user].
|: member(X, [X | L]) :- write('Evaluated first clause with X='), write(X), write('.'), nl.
|: member(X, [Y | L]) :- write('Evaluated second clause with X='), write(X), write(' and Y='), write(Y), write('.'), nl, member(X, L).
|: end_of_file.
% user://1 compiled 0.01 sec, 2 clauses
true.

?- member(1, [1, 2, 3]).
Evaluated first clause with X=1.
true .

?- member(2, [1, 2, 3]).
Evaluated second clause with X=2 and Y=1.
Evaluated first clause with X=2.
true .

?- member(4, [1, 2, 3]).
Evaluated second clause with X=4 and Y=1.
Evaluated second clause with X=4 and Y=2.
Evaluated second clause with X=4 and Y=3.
false.

?- X=1, member(X, [1, 2, 3]).
Evaluated first clause with X=1.
X = 1 .

(omitted warnings).

How about this

Note the following:

• The program is read once and then stays in memory, waiting for the user to enter a query (same as for a database scenario)
• As it executes it builds a "search tree" in memory
  • An OR node for every predicate encountered: ANY of the branches (which correspond to clauses of that predicate) must be made TRUE
  • An AND node for every clause body encountered: all the branches (which correspond to the calls made in the clause body that are seprated by ,) must be made TRUE
• The program SUCCEEDS when it can "exit at the bottom of the tree" and
  • Below any AND node, all the branches are TRUE
  • Below any OR node, at least one of the branches are TRUE (In Prolog, there is only every exactly ONE "active branch" below an OR node)
• The program eventually FAILS if no such tree can be found (which may take some time).
• On program success, the tree is kept alive in case the user ask for "more solutions"
• If you ask for "more solutions", the tree is re-entered at the bottom and alternative branches are tried.

And:

• Variable names are local to a clause
• Variable content (which is either a term or a cell with no content if the "variable is unbound" as they say) is always global. If a node deep in the tree "refines" the content of one of its variable, this change is visible at the topmost node of the tree (albeit under another name or part of another term).