prolog - 递归过程解释

Question

所以我在 Prolog 中有以下工作代码，它生成给定 A 值的阶乘:

factorial(0,1).
factorial(A,B) :- A>0, C is A-1, factorial(C,D), B is A*D.

我正在寻找有关此代码如何工作的解释。即，当您提出查询时到底会发生什么:factorial(4, Answer)。

首先，

factorial(0, 1).

我知道上面是递归定义的“基本情况”。我不确定为什么/如何这是基本情况。我的猜测是阶乘(0, 1)插入一些包含(0, 1)的结构作为“阶乘”的成员。如果是这样，其结构是什么样的？我知道如果我们说“rainy(seattle).”，这意味着西雅图正在下雨。但是“阶乘(0, 1)”... 0, 1 是阶乘吗？我意识到这意味着 0 的阶乘为 1，但从长远来看，这是如何使用的呢？ (写这篇文章可以帮助我理解更多，但我想要一些反馈以确保我的想法是正确的。)

factorial(A,B) :- A>0, C is A-1, factorial(C,D), B is A*D.

现在，上面的代码到底意味着什么？我该如何阅读？

我将其读为:如果 A>0，则 (A, B) 的阶乘为真，C 为 A-1，阶乘 (C, D)，B 为 A*D。这对我来说听起来不太正确......是吗？

“A > 0”。那么如果 A 等于 0，会发生什么？此时它不能返回，否则基本情况将永远不会被使用。所以我的猜测是 A > 0 返回 false，但其他函数最后一次执行。递归停止是因为它到达了基本情况，还是因为 A 不大于 0？或者两者的结合？在什么时候使用基本情况？

我想这可以归结为一个问题:同时具有基本情况和 A > 0 的目的是什么？

很抱歉提出了错误的问题，谢谢。

编辑:事实上，我从程序中删除了“A > 0”，代码仍然有效。所以我想我的问题至少并不愚蠢。 (该代码取自教程。)

Answer 1

从数据结构的角度来思考 Prolog 事实和规则会适得其反。当您编写 factorial(0, 1). 时，您向 Prolog 解释器断言一个事实，该事实被假定为普遍正确。仅凭这一事实，Prolog 就可以回答三种类型的问题:

• 0 的阶乘是多少？ (即factorial(0, X)；答案是X=1)
• 1 的阶乘是什么？ (即factorial(X,1)；答案是X=0)
• 0 的阶乘真的是 1 吗？ (即factorial(0,1)；答案是"is")

就 Prolog 程序的其余部分而言，只有第一个问题很重要。这是 factorial/2 规则的第二个子句在评估 factorial 结束时提出的问题。

第二条规则使用逗号运算符，这是 Prolog 表达“and”的方式。您的解释可以用变量 A 和 B 重写，如下所示:

B is a factorial of A when A>0, and C is set to A-1, and D is set to the factorial of C, and B is set to A times D

这条规则涵盖了所有大于零的A。对 factorial(C,D) 的引用将一次又一次地使用相同的规则，直到 C 达到零。此时此规则不再适用，因此 Prolog 将获取“基本情况”规则，并使用 1 作为其输出。此时，计算 Factorial(C, D) 的链开始展开，直到一直到规则的初始调用。此时，Prolog 计算最终答案，factorial/2 返回“Yes”并生成所需的输出值。

根据您的编辑，删除 A>0 仅对于获取第一个结果并不危险。一般来说，你可以让 Prolog 帮你找到更多结果。此时，删除了 A>0 的 factorial/2 会严重失败，因为它将开始沿着带有负数的第二个子句的调用链向下移动 - 一个链将以数字溢出或堆栈溢出结束的调用，以先发生者为准。