序言中递归的停止条件 [英] Stop condition for recursion in prolog

问题描述

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

Here are the facts that I have in my knowledge base (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"高的东西.

Now I want to use recursion to deduce something that is obvious "bob" is taller than "george".

我尝试添加此规则来解决此问题:

I tried to add this rule to solve this:

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

我需要你的帮助来终止这个递归，因为现在我有一个堆栈溢出错误:

I need your help to make a stop condition to this recursion because now I have a stack overflow error:

| ?- taller(bob,george).

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

谢谢

推荐答案

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

The problem is that your recursive taller/2 predicate is defined as:

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

因此，一个 taller/2 谓词可以总是在调用堆栈"上产生两个新的 taller/2 谓词，所以说话，这种嵌套可以继续下去.

As a result, a taller/2 predicate can always result in two new taller/2 predicates on the "call stack" so to speak, and this nesting can go on and on.

处理这个问题的一种方法是将知识与传递闭包分离.通过定义一个 is_taller/2 谓词，它计算 taller/2 谓词的传递闭包，如:

A way to handle this is separating the knowledge from the transitive closure. By defining an is_taller/2 predicate, that calculates the transitive closure of the taller/2 predicate like:

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是一个严格顺序关系，最终我们会到达最短的人，因此回溯会耗尽.

Now there is "guaranteed progression" so to speak, because each time the is_taller/2 is called, it will make a call to taller/2. Since taller/2 has no recursion, the number of possible answers is limited. Since taller/2 is a strict order relation, eventually we will reach the shortest person, and thus the backtracking will get exhausted.

所以完整的代码应该是:

So the full code should be:

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).

这篇关于序言中递归的停止条件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！