序言：2个数的递归乘法

Question

我不明白为什么这个乘法的递归定义正在工作。
我得到了添加部分，但在这种情况下“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). 

Answer 1

要了解谓词，尝试“读”他们在说什么。

读add/3定义第一...

add(0,X,X). 

在X添加0到X结果。

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

添加s(X)（的X后继）以Y导致Z如果添加Xs(Y)到（的Y后继）导致Z。

如果我们查看继任为增加1，那么这是说在Z(X + 1) + Y结果Z如果X + (Y + 1)结果。这在逻辑上是明显的，但似乎并没有去任何地方。然而，我们会注意到这个逻辑与add(0,X,X)的基本情况紧密结合，因为递归情况下减少第一个参数通过每次迭代删除一个连续，直到第一个参数变成0。

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

mult(0,X,0). 

乘以X结果0在0

这似乎是显而易见的。

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

通过Y结果乘以X后继在Z如果在A，和在Z添加Y到A结果X通过Y结果相乘。

如果你认为继任作为增加1，那么这是说，(X+1)*Y是Z如果X*Y为A和A+Y是Z。这是有道理的，因为(X+1)*Y是(X*Y)+Y这将是A+Y。

Answer 2

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

真的什么最终发生的是它调用addX次，每次那个时代的它增加了Y最终结果（从零开始）。这是利用乘法作为重复加法。这里是一个跟踪手工：

1. mult(3, 2, Z)
   初始呼叫

2. mult(2, 2, A_1), add(2, A_1, Z)
   减去1个FRAM 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