序言中递归的停止条件

Question

以下是我知识库中的事实（http://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpages/recursion.html（递归练习 2））：

taller(bob,mike).   % bob is taller than mike
taller(mike,jim).   % mike is taller than jim
taller(jim,george). % jim is taller than george

现在我想用递归推导出一些明显的东西 "bob" 比 "george" 高。

我尝试添加这条规则来解决这个问题：

taller(X,Y) :- taller(X,Z),taller(Z,Y).

我需要你的帮助来为这个递归设置一个停止条件，因为现在我有一个堆栈溢出错误：

| ?- taller(bob,george).

Fatal Error: local stack overflow (size: 8192 Kb, environment variable used: LOCALSZ)

谢谢

Answer 1

问题是您的递归 taller/2 谓词定义为：

taller(X,Y) :-
    taller(X,Z),
    taller(Z,Y).

因此，一个 taller/2 谓词可以总是在 "call stack" 上产生两个新的 taller/2 谓词可以这么说，并且这种嵌套可以继续下去。

处理此问题的一种方法是将知识与传递闭包分开。通过定义一个 is_taller/2 谓词，计算 taller/2 谓词的 传递闭包 如：

is_taller(X,Y) :-
    taller(X,Y).
is_taller(X,Y) :-
    taller(X,Z),
    is_taller(Z,Y).

现在可以说是“保证进展”，因为每次调用 is_taller/2 时，它都会调用 taller/2。由于 taller/2 没有递归，可能的答案数量有限。由于taller/2是strict顺序关系，最终我们会到达最矮人，这样回溯就会耗尽。

所以完整的代码应该是：

taller(bob,mike).   % bob is taller than mike
taller(mike,jim).   % mike is taller than jim
taller(jim,george). % jim is taller than george

<b>is_taller(X,Y) :-
    taller(X,Y).
is_taller(X,Y) :-
    taller(X,Z),
    is_taller(Z,Y).</b>

序言中递归的停止条件

Stop condition for recursion in prolog

recursion

prolog

transitive-closure