这是Prolog中的左递归吗？

我正在使用swipl 5.10.2。今天我开始学习我的AI课程的Prolog。我已经开始与一个非常简单的例子：这是Prolog中的左递归吗？

father(giovanni,maria). 
brother(paolo,pietro). 

grandpa(X,Y) :- 
     father(X,Z), 
     father(Z,Y). 
grandpa(X,Y) :- 
     father(X,Z), 
     mother(Z,Y). 

mother(maria,paolo). 
mother(I,J) :- 
     mother(I,K), 
     brother(K,J).

不是什么大不了的，如果我尝试这个目标grandpa(giovanni,pietro)，它的工作，这让我真正。然后我想辣迎接挑战，我修改这样的代码：

father(giovanni,maria). 
brother(paolo,pietro). 

grandpa(X,Y,Z) :- 
     father(X,Z), 
     father(Z,Y). 
grandpa(X,Y,Z) :- 
     father(X,Z), 
     mother(Z,Y). 

mother(maria,paolo). 
mother(I,J) :- 
     mother(I,K), 
     brother(K,J).

，因为我想知道中间人但是当我运行它这里发生了什么：

?- grandpa(giovanni,pietro,M). 
M = maria ; 
ERROR: Out of local stack

这是因为，imho，母亲有一个左递归，树不断发展而没有发现关闭。

然后我写了这个：

father(giovanni,maria). 
brother(paolo,pietro). 
mother(maria,paolo). 

grandpa(X,Y,Z) :- 
     father(X,Z), 
     father(Z,Y). 
grandpa(X,Y,Z) :- 
     father(X,Z), 
     mother(Z,Y). 

mother(I,J) :- 
     brother(K,J), 
     mother(I,K).

这是输出：

?- grandpa(giovanni,pietro,M). 
M = maria ; 
false.

这是正确的。那么这只是一个左递归问题，还是我错过了一些关于swipl行为的东西？当我有一个“错误：超出本地堆栈”，它总是一个递归问题？

来源

2011-02-25 dierre

我认为Out of local stack错误几乎总是（或总是）来自太深的递归;在简单的程序中，这些递归可能是无限的。代码中的问题确实是左递归问题;试图解决mother(anything, B)将尝试解决mother(anything, B1),mother(anything, B2)等等，直到您用完堆栈空间。

来源

2011-02-25 20:22:44

+1我想补充一点，最大递归深度根据处理的项的数量和大小而变化很大（如果涉及到列表，很容易按100倍），而* tail递归*是解决方案可以很大程度上避免过度使用堆栈。如果编译器支持* tail递归*，则编译器支持 – 2011-02-25 21:49:12

。就像你可以用Java那样做，但JVM不支持它，对吧？ – dierre 2011-02-27 13:53:05

虽然这段代码没有这个问题;它是一个无限递归，与是否使用尾调用无关（在这种情况下，对'mother'的规则中的目标进行重新排序可以解决问题）。 – 2011-02-27 21:58:40

这是Prolog中的左递归吗？

回答

相关问题