我們如何跟蹤序言中的遞歸算法？

Question

我覺得很unstraightforward，但我認爲我得到了它的要點，請確認我是否在錯誤與否。

append([],L,L). 
    append([H|T],L2,[H|L3]) :- append(T,L2,L3). 

下面是對規則和跟蹤的查詢。

?- append([a,b,c],[1,2,3],X) 

append([a, b, c], [1, 2, 3], _G518) 
    append([b, c], [1, 2, 3], _G587) 
    append([c], [1, 2, 3], _G590) 
    append([], [1, 2, 3], _G593) 
    append([], [1, 2, 3], [1, 2, 3]) 
    append([c], [1, 2, 3], [c, 1, 2, 3]) 
    append([b, c], [1, 2, 3], [b, c, 1, 2, 3]) 
    append([a, b, c], [1, 2, 3], [a, b, c, 1, 2, 3]) 

    X = [a, b, c, 1, 2, 3] 
    yes 

追加（T，L2，L3）， 「遞歸」 向前，削弱了列表的大小[H | T]，然後追加（[H | T]，L2，[H | L3] ）向後「遞歸」，增加列表L3的大小。所以，如果我理解正確，規則總是「向後遞歸」，其條件「遞歸」向前，我是否正確？此外，是什麼使算法向後追加「遞歸」？它追加（[]，L，L）？或者它在到達基本情況後總是「逆轉」回去？

的令人困惑的事情是，只有簡單的序言遞歸「遞歸」邁進。如果我沒有誤認爲祖先（E，F）只是「遞歸」向前。

Answer 1

這是所有關於第三個參數，X，這裏。它以大寫字母開頭，所以它是一個變量。 Prolog需要爲這個變量找到一個值。

每次append([H|T], L2, [H|L3])被調用時，它調用append(T, L2, L3)。

當append(T, L2, L3)被調用時，Prolog將首先檢查它是否適合append([], L, L)，因爲這是該程序的第一個子句。

如果它不適合，Prolog的將移動到第二條：append([H|T],L2,[H|L3])。

它適合如果第一個參數是空列表：[]。如果所有元素（本例中的字母）都已被刪除，則會發生這種情況。該子句將返回第二個參數L作爲第三個參數。從開始到結束，第二個參數始終保持[1,2,3]。它只是在這個時刻。

空列表[]是基本情況：遞歸不會去從那裏更深，因爲該條款沒有一個機構，再次呼籲append。這是找到結果（第三個參數）的第一個元素的點：L，它是[1, 2, 3]。這個結果作爲L3返回給調用它的append，它將結合它的H：[H|L3]這是[c, 1, 2, 3]。這反過來又回到稱爲那個的append。這種結果的回饋一直持續到原始的，首次調用的append得到結果。然後Prolog打印出來。

在跟蹤中，您可以看到諸如_G518之類的變量。在前三行中，基本情況尚未到達，所以第三個參數不能填寫（H是已知的，但L3不是）。