Should I avoid tail recursion in Prolog and in general?

Question

I'm working through "Learn Prolog now" online book for fun.

I'm trying to write a predicate that goes through each member of a list and adds one to it, using accumulators. I have already done it easily without tail recursion.

addone([],[]).
addone([X|Xs],[Y|Ys]) :- Y is X+1, addone(Xs,Ys).

But I have read that it is better to avoid this type of recursion for performance reasons. Is this true? Is it considered 'good practice' to use tail recursion always? Will it be worth the effort to use accumulators to get into a good habit?

I have tried to change this example into using accumulators, but it reverses the list. How can I avoid this?

accAddOne([X|Xs],Acc,Result) :- Xnew is X+1, accAddOne(Xs,[Xnew|Acc],Result).
accAddOne([],A,A).
addone(List,Result) :- accAddOne(List,[],Result).

Answer 1

Short answer: Tail recursion is desirable, but don't over-emphasize it.

Your original program is as tail recursive as you can get in Prolog. But there are more important issues: Correctness and termination.

In fact, many implementations are more than willing to sacrifice tail-recursiveness for other properties they consider more important. For example steadfastness.

But your attempted optimization has some point. At least from a historical perspective.

Back in the 1970s, the major AI language was LISP. And the corresponding definition would have been

(defun addone (xs)
  (cond ((null xs) nil)
    (t (cons (+ 1 (car xs))
         (addone (cdr xs))))))

which is not directly tail-recursive: The reason is the cons: In implementations of that time, its arguments were evaluated first, only then, the cons could be executed. So rewriting this as you have indicated (and reversing the resulting list) was a possible optimization technique.

In Prolog, however, you can create the cons prior to knowing the actual values, thanks to logic variables. So many programs that were not tail-recursive in LISP, translated to tail-recursive programs in Prolog.

The repercussions of this can still be found in many Prolog textbooks.

Answer 2

Your addOne procedure already is tail recursive.

There are no choice points between the head and the last recursive call, because is/2 is deterministic.

Accumulators are sometime added to allow tail recursion, the simpler example I can think of is reverse/2. Here is a naive reverse (nreverse/2), non tail recursive

nreverse([], []).
nreverse([X|Xs], R) :- nreverse(Xs, Rs), append(Rs, [X], R).

if we add an accumulator

reverse(L, R) :- reverse(L, [], R).
reverse([], R, R).
reverse([X|Xs], A, R) :- reverse(Xs, [X|A], R).

now reverse/3 is tail recursive: the recursive call is the last one, and no choice point is left.