How to implement tail recursion for tree algorithms in prologue
How could I convert the following to a recursive tail version.
sum(void,0).
sum(t(V,L,R),S) :-
sum(L,S1),
sum(R,S2),
S is V + S1 + S2.
It seems impossible to maintain a single battery since the fork has a magnitude of 2 ^ n.
A possible solution is for the accumulator to add a new drive to the list at each iteration. Maybe the solution above is optimal?
Thanks in advance.
+2
source to share
1 answer
Yes, your solution is optimal because it will call the sum / 2 predicate exactly once for every node in the tree (and you just can't make fewer calls). No, you can make it tail-recursive by executing the stack itself with an accumulator.
Here's an example (not tested). The flatten predicate can be integrated with the sum, but here they differ for clarity (both are tail recursive):
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).
+2
source to share