Prolog：2个数的递归乘法

Prolog: Recursive Multiplication of 2 Numbers

我不明白为什么这个乘法的递归定义有效。
我得到了添加部分，但是 "A" 在这种情况下的价值如何。 代码如下：

add(0,X,X).
add(s(X),Y,Z):-add(X,s(Y),Z).

mult(0,X,0).
mult(s(X),Y,Z):-mult(X,Y,A), add(Y,A,Z).

要理解谓词，请尝试 "read" 他们在说什么。

首先阅读 add/3 定义...

add(0,X,X).

Adding 0 to X results in X.

add(s(X),Y,Z):-add(X,s(Y),Z).

Adding s(X) (the successor of X) to Y results in Z if adding X to s(Y) (the successor of Y) results in Z.

如果我们将 successor 视为加 1，那么这就是说 (X + 1) + Y 导致 Z 如果 X + (Y + 1) 导致 Z.这在逻辑上是显而易见的，但似乎没有任何意义。但是，我们会注意到此逻辑与 add(0,X,X) 的基本情况密切相关，因为递归情况将 减少 第一个参数，方法是每次迭代删除一个连续性，直到第一个参数变为 0.

现在让我们试试mult/3...

mult(0,X,0).

Multiplying 0 by X results in 0

这似乎是显而易见的。

mult(s(X),Y,Z):-mult(X,Y,A), add(Y,A,Z).

Multiplying the successor of X by Y results in Z if multiplying X by Y results in A, and adding Y to A results in Z.

如果你认为successor加1，那么这就是说(X+1)*Y是Z如果X*Y是A 并且 A+Y 是 Z。这是有道理的，因为 (X+1)*Y 是 (X*Y)+Y 也就是 A+Y.

在此上下文中，A 是 (X-1) * Y 的值。您使用 mult 规则递归地找到此值，然后将其添加到 add 规则中的 Y 以获得最终结果。它将乘法写为 X * Y = (X - 1) * Y + Y

实际上最终发生的是它调用 add X 次，并且每次都将 Y 添加到最终结果（从零开始）。这是利用乘法作为重复加法。这是手工跟踪：

  1. mult(3, 2, Z)
    初次通话

  2. mult(2, 2, A_1), add(2, A_1, Z)
    减去 1 帧 X

  3. mult(1, 2, A_2), add(2, A_2, A_1)
    再次.

  4. mult(0, 2, A_3), add(2, A_3, A_2)
    最后一次

  5. mult(0, 2, A_3)
    只有一种可能，因为零无法匹配 s(x)。 A_3 设置为 0。

  6. mult(0, 2, 0), add(2, 0, A_2)
    第 4 步，但用 A_3 替换。我们现在知道 A_2 一定是 2.

  7. mult(1, 2, 2), add(2, 2, A_1)
    第 3 步，但用 A_2 替换。我们现在知道 A_1 必须是 4.

  8. mult(2, 2, 4), add(2, 4, Z)
    第 2 步，但用 A_1 替换。我们现在知道Z一定是6，就是最后的结果。

对于第 2 步到第 4 步，您可以通过倒数来计算需要重复加法运算的次数。第 5 步是基本情况，最终结果从零开始。在步骤 6 到 8 中执行添加。这给出了 Z = 6 = 2 + 2 + 2

的结果