我应该避免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中获得原始程序的尾递归.但还有更重要的问题:正确性和终止性.

实际上,许多实现都非常愿意为他们认为更重要的其他属性牺牲尾递归.例如坚定不移.

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

早在20世纪70年代,主要的AI语言就是LISP.相应的定义也是如此

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

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

但是,在Prolog中,您可以在了解实际值之前创建缺点,这要归功于逻辑变量.如此多的程序在LISP中不是尾递归的,转换为Prolog中的尾递归程序.

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

Answer 2

你的addOne过程已经是 tail递归的.

头部和最后一个递归调用之间没有选择点,因为/ 2是确定性的.

有时会添加累加器以允许尾递归,我能想到的更简单的例子是reverse/2.这是一个天真的反向(nreverse/2),非尾递归

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

如果我们添加一个累加器

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

现在reverse/3是尾递归的:递归调用是最后一个,没有选择点.