4

以下是我的知识库中的事实（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

现在我想用递归来推断出明显的“鲍勃”比“乔治”高。

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

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

我需要您的帮助来为此递归设置停止条件，因为现在我遇到了堆栈溢出错误：

| ?- taller(bob,george).

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

谢谢

4

1 回答 1

7

问题是您的递归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).
于 2017-06-15T01:59:13.680 回答