recursion - 用递归调用替换序言基本情况

Question

我是 Prolog 的新手，最近开始使用这本很棒的书来学习它 Learn Prolog Now! .有一些我不完全理解的东西，这真的困扰着我。 exercises其中之一问题是

我们有以下知识库和谓词:

child(anne,bridget).
child(bridget,caroline).
child(caroline,donna).
child(donna,emily).

descend(X,Y)  :-  child(X,Y).
descend(X,Y)  :-  child(X,Z),
                  descend(Z,Y).

如果我们将谓词更改为以下内容会发生什么:

descend(X,Y)  :-  child(X,Y).
descend(X,Y)  :-  descend(X,Z),
                  descend(Z,Y).

我知道这会导致错误案例的无限递归，但我无法完全理解为什么。

如果我理解正确，在上面的第一种情况下，如果给出错误查询 child(X,Z)将穷尽其所有选项尝试将多个元素统一到 Z 然后失败，回溯到前一个 X 然后再次尝试 Z 的选项以满足 child(X, Z)。 (如果我错了，请纠正我)。

我不确定为什么对于下降谓词的第二个定义不会发生同样的情况。

Answer 1

让我们花点时间将您显示的片段缩减为 片段这清楚地表明了不终止的原因。

初始片段是您发布的整个程序:

下降(X，Y): - child (X，Y)。
下降(X，Y): - 下降(X，Z)，
下降(Z，Y)。

现在，我们插入 false/0 在某些地方。例如:

下降(X，Y): - 假， child (X，Y)。
下降(X，Y): - 下降(X，Z)，
错误的，
下降(Z，Y)。

我正在使用删除文本来指示对终止没有影响的程序部分。也就是说，我们实际上最终得到:

下降(X，Y): - 下降(X，Z)。

仅此片段就已导致非终止 .您没有添加任何纯粹的条款，并且没有任何遵循单一目标的东西可以阻止它!因此，要终止此操作，您必须更改此片段。

见 failure-slice想要查询更多的信息。