遞迴

Created: November-22, 2018

Prolog 沒有迭代，但所有迭代都可以使用遞迴重寫。當謂詞包含引用自身的目標時，將出現遞迴。在 Prolog 中編寫這樣的謂詞時，標準的遞迴模式總是至少包含兩部分：

Base（非遞迴）子句 ：通常，基本情況規則將代表你嘗試解決的問題的最小可能示例 - 沒有成員的列表，或者只有一個成員，或者如果你’正在使用樹結構，它可能處理一個空樹，或者只有一個節點的樹，等等。它非遞迴地描述了遞迴過程的基礎。
遞迴（continue）子句 ：包含任何必需的邏輯，包括對自身的呼叫，繼續遞迴。

作為一個例子，我們將定義眾所周知的謂詞 append/3。以宣告方式檢視，當列表 L3 是附加列表 L1 和 L2 的結果時，append(L1,L2,L3) 成立。當我們試圖找出謂詞的宣告性含義時，我們試圖描述謂詞所持有的解決方案。這裡的困難在於試圖避免任何逐步重複出現的細節，同時仍然牢記謂詞應該表現出的程式行為。

% Base case
append([],L,L).

% Recursive clause
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

基本情況以宣告方式宣告“附加到空列表的任何 L 是 L”，請注意，這並不表示 L 是空的 - 甚至不是列表（請記住，在 Prolog 中，所有內容都歸結為術語）：

?- append(X,some_term(a,b),Z).
X = [],
Z = some_term(a, b).

為了描述遞迴規則，雖然 Prolog 從左到右執行規則，但是我們先省略頭部並首先檢視正文 - 從右到左閱讀規則：

    append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

現在我們說，如果身體持有：“假設 append(L1,L2,L3) 持有”

    append([X|L1],L2,[X|L3]) :-  append(L1,L2,L3).

頭腦也是如此：“那麼 append([X|L1],L2,[X|L3])”

用簡單的英語，這只是轉換為：

假設 L3 是 L1 和 L2 的串聯，那麼[X 後跟 L3]也是[X 後跟 L1]和 L2 的串聯。

在一個實際例子中：

“假設[1,2,3]是[1]和[2,3]的串聯，那麼[a，1,2,3]也是[a，1]和[2,3]的串聯。 ”

現在讓我們看一些查詢：

最初使用最常見的查詢測試謂詞而不是為其提供特定的場景測試用例總是一個好主意。想一想：由於 Prolog 的統一，我們不需要提供測試資料，我們只需提供自由變數！

?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;                                   % Answer #1
L1 = [_G1162],
L3 = [_G1162|L2] ;                          % Answer #2
L1 = [_G1162, _G1168],
L3 = [_G1162, _G1168|L2] ;                  % Answer #3
L1 = [_G1162, _G1168, _G1174],
L3 = [_G1162, _G1168, _G1174|L2] ;          % Answer #4
...

讓我們用字母替換自由變數 _G1162-like 表示法以獲得更好的概述：

?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;                                   % Answer #1
L1 = [_A],
L3 = [_A|L2] ;                              % Answer #2
L1 = [_A, _B],
L3 = [_A, _B|L2] ;                          % Answer #3
L1 = [_A, _B, _C],
L3 = [_A, _B, _C|L2] ;                      % Answer #4
...

在第一個答案中，基本案例是模式匹配的，Prolog 將 L1 例項化為空列表並統一 L2 和 L3，證明 L3 是空列表和 L2 的串聯。

在答案#2，通過按時間順序回溯，遞迴子句發揮作用，Prolog 試圖證明 L1 頭部中與 L2 連線的某個元素是 L3，其列表頭中具有相同的元素。為此，一個新的自由變數 _A 與 L1 的頭部統一，L3 被證明現在是 [_A|L2]。

現在使用 L1 = [_A] 進行新的遞迴呼叫。再一次，Prolog 試圖證明放在 L1 頭部的一些元素與 L2 連線的是 L3，頭部中有相同的元素。請注意，_A 已經是 L1 的頭部，它完全符合規則，所以現在，通過遞迴，Prolog 將 _A 放在一個新的自由變數前面，我們得到 L1 = [_A,_B] 和 L3 = [_A,_B|L2]

我們清楚地看到遞迴模式重複自身並且可以很容易地看到，例如，遞迴中的第 100 步的結果將如下所示：

L1 = [X1,X2,..,X99],
L3 = [X1,X2,..,X99|L2]

注意：正如典型的 Prolog 程式碼一樣，append/3 的遞迴定義不僅為我們提供了驗證列表是否是另外兩個列表的串聯的可能性，它還生成了滿足與完全或部分邏輯關係的所有可能答案例項化列表。