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

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

Prolog的截斷機制與謂詞fail

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

例如，考慮以下規(guī)則：

```prolog

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

```

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

正確選擇遞歸規(guī)則和停止條件

在編寫Prolog程序時，一個謂詞通常以多種形式存在，其中一般至少有兩種不同形式的謂詞。這包括遞歸規(guī)則和停止條件。當(dāng)編寫這樣的謂詞時，必須確保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.

```

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

```prolog

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

```

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

使用截斷避免無限遞歸

上述情況顯然不是我們所期望的。然而，可以通過在停止條件中設(shè)置截斷來避免這種情況的發(fā)生。下面給出了更加健全和可靠的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.

```

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

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

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