在prolog中停止递归的条件

Question

以下是我在知识库中的事实(http://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpages/recursion.html(Recursion Exercise 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谓词总是可以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).