recursion - 递归数据记录的执行顺序是什么？

Question

Q(a, b) :- Edge(a, b).
Q(a, b) :- Q(a, x),
            Edge(x, b).

此代码的功能是搜索所有可到达的节点对。那是如何递归的？

标签： recursiondatalog

Answer 1

这是递归的，因为谓词调用自身：

q(A, B) :- q(A, X),edge(X, B).

实际的执行顺序取决于实现。它可能是“自下而上”的：

• 从任何edge(A,B)派生q(A,B)
• 应用q(A, B) :- q(A, X),edge(X, B).直到达到固定点（即不能进一步q(A,B)推断）。

但是，与 Prolog 不同，您应该能够重新排列代码而不会产生非终止搜索的风险。

这也应该有效：

q(A, B) :- q(A, X),edge(X, B).
q(A, B) :- edge(A, B).