Learn

Pure functional recursion in Prolog can be slow because it builds the answer on the way OUT of the recursion. Accumulators flip this — pass partial results IN, build answer on the way IN.

Naive sum — O(n) but inefficient (no tail call):

sum([], 0).
sum([H|T], S) :- sum(T, S1), S is H + S1.

With accumulator — tail-recursive, much faster:

sum_acc([], Acc, Acc).
sum_acc([H|T], Acc, S) :-
    NewAcc is Acc + H,
    sum_acc(T, NewAcc, S).

%% Helper that hides the accumulator:
sum(L, S) :- sum_acc(L, 0, S).

The accumulator (Acc) carries the partial result. The base case copies it to the output. This is the same trick as left fold in functional languages.

Reverse with accumulator — naive reverse is O(n²):

%% Bad — quadratic
reverse_naive([], []).
reverse_naive([H|T], R) :-
    reverse_naive(T, RT),
    append(RT, [H], R).      %% append is O(n) per step

%% Good — linear
reverse_acc([], Acc, Acc).
reverse_acc([H|T], Acc, R) :-
    reverse_acc(T, [H|Acc], R).

reverse(L, R) :- reverse_acc(L, [], R).

Prepending ([H|Acc]) is O(1); appending (append(T, [H], R)) is O(n). The accumulator pattern lets you flip the building direction.

Most stdlib predicates (length/2, msort/2, sumlist/2) are implemented with accumulators internally. When writing recursive list code, prefer accumulators for performance.