我正在学习Prolog，我在递归方面遇到了困难。我可以理解数据库的简单案例，但我不能遵循这个练习，其中实现了redu/2，它将删除给定列表的重复项，并将新列表作为第二个参数：
redu([],[]).
redu([H|T], Result):-
member(H,T),
redu(T,Result).
redu([H|T], [H|Result]):-
redu(T, Result).
一个痕迹给了我这个：
[trace] ?- redu([a,b,b,c,a], X).
Call: (8) redu([a, b, b, c, a], _35630) ? creep
Call: (9) lists:member(a, [b, b, c, a]) ? creep
Exit: (9) lists:member(a, [b, b, c, a]) ? creep
Call: (9) redu([b, b, c, a], _35630) ? creep
Call: (10) lists:member(b, [b, c, a]) ? creep
Exit: (10) lists:member(b, [b, c, a]) ? creep
Call: (10) redu([b, c, a], _35630) ? creep
Call: (11) lists:member(b, [c, a]) ? creep
Fail: (11) lists:member(b, [c, a]) ? creep
Redo: (10) redu([b, c, a], _35630) ? creep
Call: (11) redu([c, a], _35900) ? creep
Call: (12) lists:member(c, [a]) ? creep
Fail: (12) lists:member(c, [a]) ? creep
Redo: (11) redu([c, a], _35900) ? creep
Call: (12) redu([a], _35906) ? creep
Call: (13) lists:member(a, []) ? creep
Fail: (13) lists:member(a, []) ? creep
Redo: (12) redu([a], _35906) ? creep
Call: (13) redu([], _35912) ? creep
Exit: (13) redu([], []) ? creep
Exit: (12) redu([a], [a]) ? creep
Exit: (11) redu([c, a], [c, a]) ? creep
Exit: (10) redu([b, c, a], [b, c, a]) ? creep
Exit: (9) redu([b, b, c, a], [b, c, a]) ? creep
Exit: (8) redu([a, b, b, c, a], [b, c, a]) ? creep
X = [b, c, a]
如果有人能用自然语言向我解释递归的作用以及如何阅读子句，我将不胜感激。就像第二个子句一样，它读起来是“从列表H|T中删除重复项并输出Result，如果该列表的头部是尾部的成员，并从尾部删除重复项并输出结果？但是两个结果怎么可能是相同的呢？我也不知道哪个规则在什么时候被激活。它在我的子句列表中什么时候前进？什么时候返回？
抱歉所有的问题。我真的很想了解一切。
所以你有
redu([], []).
redu([H|T], R ):- member(H, T), redu(T, R).
redu([H|T], [H|R]):- redu(T, R).
==
redu([], []).
redu([H|T], X ):- member(H, T), X = R , redu(T, R).
redu([H|T], X):- X = [H|R], redu(T, R).
==
redu([], []).
redu([H|T], X ):- ( member(H, T), X = R ; X = [H|R]), redu(T, R).
==
redu([], []).
redu([H|T], X ):- disj(H, T, X, R), redu(T, R).
disj(H, T, R, R):- member(H, T).
disj(H,_T, [H|R], R).这两个新的redu/2子句是互斥的，所以这种形式的代码更容易理解。无论disj/4是否将H包含在正在构建的列表X中（以自上而下的方式）-无论它成功多少次 (*) - 在disj/4完成它的事情之后，对redu/2的递归调用都是简单的。
因此，我们将redu（L， X）读为“对于L=[H|T]中的头元素H，如果T中有更多的H，要么不将H包含在“输出”列表X中，要么这样做；对于唯一的H-这样不会出现在T中-始终将其包含在X中；然后，在处理了L的这个头元素H之后，继续处理L中的其余元素列表以相同的方式。"换句话说，对列表L中的每个元素执行此操作。
这个递归定义自然遵循列表的归纳定义，即[H|T]或[]结构。
（*）（请注意A.成员可能不止一次成功，B.disj/4的两个子句不是互斥的）。
以你为例，
redu([a,b,b,c,a], X)
==
disj( a, [b,b,c,a], X,R), % AND redu([b,b,c,a], R) i.e.
disj( b, [b,c,a], R,R2), % AND redu([b,c,a], R2) i.e.
disj( b, [c,a], R2,R3), % AND redu([c,a], R3) i.e.
disj( c, [a], R3,R4), % AND redu([a], R4) i.e.
disj( a, [], R4,R5), % AND the final clause,
redu( [], R5).现在您可以尝试每个disj/4调用并查看那里发生了什么，例如
33 ?- disj(a,[b,b,c,a], X,R).
X = R ;
X = [a|R].
34 ?- disj(b,[c,a], R2,R3).
R2 = [b|R3].
这样整个例子就变成了
(X = R ; X = [a|R]), % [ a
(R = R2 ; R = [b|R2]), % b
R2 = [b|R3], % b
R3 = [c|R4], % c
R4 = [a|R5], % a
R5 = []. % ]或
ex(X):-
(X = R ; X = [a|R]),
(R = R2 ; R = [b|R2]),
R2 = [b,c,a].
这是
42 ?- ex(X).
X = [b, c, a] ;
X = [b, b, c, a] ;
X = [a, b, c, a] ;
X = [a, b, b, c, a].
任何递归实现都至少有两个子句——基础子句和一个或多个递归子句。
基本子句处理退化情况：空列表、零等。它们给出简单的答案——例如，在您的情况下，基本子句指出空列表的答案是空列表。
递归子句分别处理项目在列表中（第二个子句）和项目不在列表中（第三个子句）的情况。第二个子句说，当在列表的尾部找到一个项目（T的成员）时，它不应该现在添加到结果中；它将在以后添加。另一方面，如果这是最后一项，第三个子句将其添加到输出列表中。
但是，最终，成员检查会失败（b不是[c， a]的成员），但是它是如何工作的呢？
一旦成员检查失败，Prolog就会转到第三个子句，它将H添加到带有[H|Result]的输出列表中，并继续使用redu（T， Result）从列表的尾部T计算Result的其余部分。
注意1：程序中有一个错误：最后一个子句需要以项目不在列表的尾部为条件：
redu([H|T], [H|Result]):-
\+ member(H,T),
redu(T, Result).
如果第二个子句已经执行，这应该可以防止Prolog进入子句。
注2：另一个选项是在第二个子句中使用剪切，但此选项非常不鼓励。
