Prolog에서 트리 알고리즘에 대한 꼬리 재귀를 구현하는 방법

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 Prectice를 호출하기 때문에 최적입니다 (그리고 단순히 전화를 걸 수 없음). 아니요, 축합기를 사용하여 스택을 직접 구현하여 테일 리퍼 시브로 만들 수 있습니다.

다음은 예입니다 (테스트되지 않음). 평평한 술어는 합계와 통합 될 수 있지만 여기서는 명확성을 위해 뚜렷합니다 (둘 다 꼬리 수반입니다).

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