Prolog同名递归谓词查询不终止及结果缺失问题求解

问题根源解析 #

1. 查询不终止的原因 #

你使用同名谓词同时定义基础事实和左递归规则，触发了Prolog深度优先搜索的无限循环：

• Prolog匹配目标时按代码顺序从上到下检索，当所有progeny事实匹配完成后，会命中你写的递归规则：progeny(X, Y) :- progeny(X, Z), progeny(Z, Y)
• 该规则右部第一个目标和左部谓词完全一致，会再次从头匹配所有progeny定义，匹配完事实后又会重新触发递归规则，无限循环无法终止。

2. progeny(Y, lisa)缺少mark结果的原因 #

Prolog对规则右部的目标按从左到右的顺序求值：

• 首先匹配基础事实得到第一个结果Y=bill
• 进入递归规则后，第一个目标progeny(X,Z)先匹配到progeny(dexter, mark)，第二个目标匹配到progeny(mark, lisa)，得到第二个结果Y=dexter
• 继续检索时，progeny(X,Z)会命中递归分支进入无限循环，程序卡死在递归展开环节，还没走到progeny(mark,bill)+progeny(bill,lisa)的匹配逻辑，所以Y=mark的结果无法返回。

修复方案 #

不要把直接关系和传递关系的定义放在同一个谓词下，拆分谓词避免左递归即可：

% 直接亲子事实
parent(dexter, mark).
parent(mark, bill).
parent(bill, lisa).

% 传递后代规则：优先匹配直接关系，再匹配间接关系
progeny(X, Y) :- parent(X, Y).
progeny(X, Y) :- parent(X, Z), progeny(Z, Y).

修改后所有查询都会正常返回所有结果，且执行完成后自动终止。

内容的提问来源于stack exchange，提问作者No_Name