recursion - Prolog递归乘法

Question

我正在尝试递归地将 Prolog 中的两个数字相乘，即 3*4 = 3+3+3+3 = 12。

我的代码是:

mult(0,Y,Y).
mult(X,Y,Z) :- 
    NewX is X-1, 
    Z is Y + mult(NewX,Y,Z).

但我要么陷入无限循环，要么被告知 mult 不是函数。

Answer 1

您在这里构造的是一个谓词。谓词不与计算机科学中的函数相同，您不能写A is B + some_pred(C)，或者至少据我所知不是ISO Prolog，绝对不是没有添加一些额外的逻辑。

为了传递值，我们使用变量。因此，我们可以调用 mult/3 谓词递归，并使用一个与结果统一的变量。然后我们可以用它执行算术运算，例如:

mult(0, _, 0).
mult(X, Y, Z) :-
    X1 is X - 1,
    mult(X1, Y, <b>Z1</b>),
    Z is Y + <b>Z1</b>.

请注意，您不能将(不同的)值重新分配给变量。因此，如果像您在问题中所做的那样，使用 Z 两次，然后给定 Y 不是 0，这将失败。

然而，以上仍然不够，因为它会产生一个结果，但随后会陷入无限循环，因为如果它(最终)调用 mult(0, 4, Z) (4 在这里只是一个值)，有两种方法可以解决这个问题:基本情况和递归情况。

因此，对于第二种情况，我们需要一个“守卫”，例如:

mult(0, _, 0).
mult(X, Y, Z) :-
    <b>X > 0</b>,
    X1 is X - 1,
    mult(X1, Y, Z1),
    Z is Y + Z1.

然后我们得到例如:

?- mult(14, 25, Z).
Z = 350 ;
false.

可以通过实现带有累加器 的版本来提高这个mult/3 谓词的速度。我把它留作练习。