我应该避免使用Prolog和一般的尾递归吗？

2018-06-28 19:58:15

我正在通过“Learn Prolog now”在线书籍寻找乐趣。

我试图写一个谓词来遍历列表中的每个成员，并使用累加器添加一个谓词。我已经很容易地做到了，而且没有尾递归。

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中获得的尾部递归。但还有更重要的问题：正确性和终止。

事实上，许多实现都愿意牺牲他们认为更重要的其他属性的尾递归。例如坚定。

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

早在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教科书中找到。

您的addOne过程已经是尾递归。

头部和最后一次递归调用之间没有选择点，因为/ 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).

现在反向/ 3是尾递归：递归调用是最后一个，并且没有选择点。

OP说：

但是我已经读过，为了性能原因避免[tail]递归更好。这是真的？总是使用尾递归是否被认为是“良好实践”？使用累加器来养成良好习惯是否值得努力？

将尾递归构造转换为迭代（循环）是一种相当直接的优化。由于tail（递归）调用是最后一件事情，因此可以在递归调用中重用栈帧，通过简单地跳转到谓词/函数/方法的开始，为所有意图和目的制作循环，一个循环/子程序。因此，尾递归谓词不会溢出堆栈。尾递归构造，应用了优化有以下好处：

由于不需要分配/释放新的堆栈帧，所以执行速度稍快; 此外，你会得到更好的参考位置，所以可以说分页更少。

递归的深度没有上限。

没有堆栈溢出。

可能的缺点？

有用的堆栈跟踪丢失。如果TRO仅适用于发布/优化版本而不是调试版本，则不是问题，但...

开发人员将编写依赖于TRO的代码，这意味着代码可以正常运行，应用TRO时会失败，而不会应用TRO。这意味着在上述情况下（TRO仅在发布/优化版本中），在版本和调试版本之间存在功能变化，这基本上意味着编译器选项的选择会从相同的源代码生成两个不同的程序。

当语言标准要求尾递归优化时，这当然不是问题。

引用维基百科：

尾调用非常重要，因为它们可以在调用堆栈中不添加新栈帧的情况下实现。当前过程的大部分帧不再需要了，它可以被尾部调用的帧所替代，并根据需要进行修改（类似于进程的叠加，但是对于函数调用）。程序然后可以跳转到被调用的子程序。产生这样的代码而不是标准的呼叫序列称为尾部呼叫消除或尾部呼叫优化。

也可以看看：

什么是尾巴呼叫优化？

关于此事的波特兰模式库

甚至微软的MSDN

我从来没有理解为什么更多的语言不实现尾递归优化

链接地址: http://www.djcxy.com/p/80515.html