recursion - 在序言中停止递归的条件

这是我的知识库中的事实(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)

谢谢

最佳答案

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

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

结果，一个taller/2谓词总是可以在“调用堆栈”上产生两个新的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是严格的顺序关系，最终我们将到达最短的人，因此回溯将变得筋疲力尽。

因此完整的代码应为:

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

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