序言：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