How to implement tail recursion for tree algorithms in prolog.

Question

How could I convert the following into a tail recursive 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 accumulator as the branching is in 2^n magnitude.

A possible solution would be to have the accumulator add a new accumulator to a list on each iteration. Maybe the above solution is optimal?

Thanks in advance.

Answer 1

Yes, your solution is optimal, because it will call sum/2 predicate exactly once for each node in tree (and you simply cannot make less calls). No, you can make it tail-recursive, by implementing the stack yourself using an accumulator.

Here's an example (not tested). The flattening predicate could be integrated with sum, but here they are distinct 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).