如何在序言中实现树算法的尾递归

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).