Как реализовать хвостовую рекурсию для алгоритмов дерева в прологе - PullRequest
Новая
       29

Как реализовать хвостовую рекурсию для алгоритмов дерева в прологе

2 голосов
/ 05 октября 2009

Как я могу преобразовать следующее в хвостовую рекурсивную версию. 

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

Кажется невозможным поддерживать один аккумулятор, поскольку разветвленность имеет величину 2 ^ n.

Возможным решением было бы добавление аккумулятора в список на каждой итерации. Может быть, приведенное выше решение является оптимальным?

Заранее спасибо.

1 Ответ

2 голосов
/ 06 октября 2009

Да, ваше решение оптимально, потому что оно будет вызывать предикат sum / 2 ровно один раз для каждого узла в дереве (и вы просто не сможете делать меньше вызовов). Нет, вы можете сделать его рекурсивным, реализовав стек самостоятельно с помощью аккумулятора.

Вот пример (не тестировался). Предикат уплощения может быть интегрирован с суммой, но здесь они отличаются для ясности (оба являются хвостово-рекурсивными): 

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