在Prolog的遞歸中，我們經常會用到截斷。盡管回溯是Prolog中最有用的機制之一，但有時我們希望利用截斷來控制回溯的程序。Prolog的截斷機制與謂詞failProlog為用戶提供了一種可存在于程

在Prolog的遞歸中，我們經常會用到截斷。盡管回溯是Prolog中最有用的機制之一，但有時我們希望利用截斷來控制回溯的程序。

Prolog的截斷機制與謂詞fail

Prolog為用戶提供了一種可存在于程序中并控制回溯水平的機制，即所謂的“截斷（cut）”。在Prolog中，截斷使用嘆號“!”來表示。當在幾個目標合取中設置了截斷時，它就像是放置了一扇單向門。截斷作為目標總是成功的，并且不能重復滿足。

例如，考慮以下規則：

```prolog

example :- a, b, c, !, d, e, f.

```

在這個例子中，Prolog可以在目標a、b、c之間任意回溯，但一旦目標c被滿足后，通過截斷符號“!”，Prolog將繼續嘗試滿足目標d、e、f，而不會回溯到c之前的目標。即使導致整體目標example失敗，也不會回溯到“!”的位置。

正確選擇遞歸規則和停止條件

在編寫Prolog程序時，一個謂詞通常以多種形式存在，其中一般至少有兩種不同形式的謂詞。這包括遞歸規則和停止條件。當編寫這樣的謂詞時，必須確保Prolog總是選擇謂詞的正確形式。

例如，考慮以下用于計算X的Y次冪的程序：

```prolog

power(_, 0, 1).

power(X, Y, Pow) :- Y_tmp is Y - 1, power(X, Y_tmp, Pow_tmp), Pow is Pow_tmp * X.

```

如果我們向Prolog提出詢問：

```prolog

?- power(2, 3, Result).

```

Prolog將以以下方式進行操作：

```

Result 2 * 2 * 2,

4 * 2,

8.

```

但如果我們要求上述回答后繼續回溯，即在輸入分號時，Prolog將試圖在知識庫中尋找另一個事實或規則，使其與上面的目標匹配。在這種情況下，Prolog將找到另一個遞歸規則，即：

```prolog

power(X, Y_tmp, Pow_tmp) :- power(X, Y_tmp, Pow_tmp), ...

```

Prolog將繼續匹配該規則，使X為2，Y_tmp為0，然后Prolog計算Y_tmp得到-1，并試圖滿足目標：`power(X, Y_tmp, Pow_tmp)`。這等于在計算2的-1次冪，然后繼續計算2的-2次冪，2的-3次冪等等。這時無窮遞歸出現了，即遞歸目標連續產生自身，而永遠不能滿足停止條件，從而導致錯誤。

使用截斷避免無限遞歸

上述情況顯然不是我們所期望的。然而，可以通過在停止條件中設置截斷來避免這種情況的發生。下面給出了更加健全和可靠的power謂詞形式：

```prolog

power(_, 0, 1) :- !.

power(X, Y, Pow) :- Y_tmp is Y - 1, power(X, Y_tmp, Pow_tmp), Pow is Pow_tmp * X.

```

在這個新的謂詞形式中，截斷符號“!”表示“如果已經選擇了某個規則，那么決不允許回溯并選擇同一謂詞的其他規則”。因此，這將產生合理的結果，并避免了無限遞歸的問題。

類似地，如果有其他遞歸規則可能產生類似不希望的結果，可以通過在它們的停止條件中分別添加截斷來避免這種情況的發生。

總結來說，如果在停止條件中可能需要使用遞歸規則，請務必在遞歸謂詞的停止條件中加入截斷符號，以避免無限遞歸的問題。