如何在序言中實現樹算法的尾遞歸

Question

如何將以下內容轉換爲尾遞歸版本。

sum(void,0). 
sum(t(V,L,R),S) :- 
    sum(L,S1), 
    sum(R,S2), 
    S is V + S1 + S2. 

似乎不可能維持一個單一的累加器，因爲分支是2^n的大小。

一個可能的解決方案是讓累加器在每次迭代時爲列表添加一個新的累加器。 也許上述解決方案是最佳的？

在此先感謝。

Answer 1

是的，你的解決方案是最優的，因爲它會爲樹中的每個節點調用sum/2謂詞一次（並且你無法減少調用）。不，您可以通過使用累加器自己實現堆棧來實現尾遞歸。

下面是一個示例（未測試）。扁平化謂詞可以與sum相結合，但爲了清晰起見，它們是不同的（均爲尾遞歸）：

flatten([],   Acc, Acc). 
flatten([void|ToGo], Acc, Result) :- 
    flatten(ToGo, Acc, Result). 
flatten([t(V,L,R)|ToGo], Acc, Result) :- 
    flatten([L,R|ToGo], [t(V,L,R)|Acc], Result). 

flatten(Root, Result) :- 
    flatten([Root], [], Result). 

sum([], Result, Result). 
sum([t(V,_,_)|ToGo], Acc, Result) :- 
    NewAcc is Acc+V, 
    sum(ToGo, NewAcc, Result). 

sum(Tree, Result) :- 
    flatten(Tree, FlatTree), 
    sum(FlatTree, 0, Result).