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

Question

为了好玩，我正在阅读“立即学习 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).

Answer 1

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

您的原始程序与 Prolog 中的尾递归一样。但还有更重要的问题:正确性和终止。

事实上，许多实现非常愿意为了其他他们认为更重要的属性而牺牲尾递归。例如 steadfastness .

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

早在 1970 年代，主要的 AI 语言是 LISP。相应的定义应该是

(defun addone (xs)
(cond ((null xs) nil)
(t (缺点 (+ 1 (汽车 xs))
(addone (cdr xs))))))

这不是直接尾递归的:原因是 cons :在那个时候的实现中，它的参数首先被评估，然后才是 cons可以被执行。因此，按照您的指示重写(并反转结果列表)是一种可能的优化技术。

然而，在 Prolog 中，您可以在知道实际值之前创建缺点，这要归功于逻辑变量。很多在 LISP 中不是尾递归的程序，在 Prolog 中转换为尾递归程序。

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