我应该在 Prolog 和一般情况下避免尾递归吗？

我正在阅读“立即学习 Prolog”在线书籍，以获取乐趣。

我正在尝试编写一个谓词，该谓词遍历列表的每个成员并向其添加一个，使用累加器。我已经在没有尾递归的情况下轻松完成了。

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

但我读到出于性能原因最好避免这种类型的递归。这是真的？始终使用尾递归是否被认为是“良好实践”？使用累加器来养成一个好习惯值得付出努力吗？

我尝试将此示例更改为使用累加器，但它颠倒了列表。我怎样才能避免这种情况？

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

简短的回答：尾递归是可取的，但不要过分强调它。

您的原始程序是 Prolog 中可以得到的尾递归程序。但还有更重要的问题：正确性和终止。

事实上，许多实现非常愿意为了他们认为更重要的其他属性而牺牲尾递归性。例如坚定 https://stackoverflow.com/q/13100364/772868.

但您尝试的优化有一定的意义。至少从历史的角度来看是这样。

早在 20 世纪 70 年代，主要的人工智能语言是 LISP。相应的定义是

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

这不是直接尾递归：原因是cons：在当时的实现中，首先评估其参数，然后才评估cons可以被执行。因此，按照您的指示重写此内容（并反转结果列表）是一种可能的优化技术。

然而，在 Prolog 中，借助逻辑变量，您可以在了解实际值之前创建 cons。很多在 LISP 中不是尾递归的程序在 Prolog 中被转换为尾递归程序。

这种影响仍然可以在许多 Prolog 教科书中找到。