我应该避免在Prolog中以及一般情况下进行尾递归吗？ [英] Should I avoid tail recursion in Prolog and in general?

问题描述

我正在研究立即学习Prolog在线图书，很有趣。

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).

推荐答案

简短答案：尾部递归是可取的，但是不要

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

您的原始程序就像可以在Prolog中获得的尾部递归一样。但是还有更多重要的问题：正确性和终止性。

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.

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

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))))))

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

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.

但是，在Prolog中，您可以在了解实际情况之前创建缺点。值，这要归功于逻辑变量。这么多在LISP中不是尾递归的程序，在Prolog中已翻译为尾递归程序。

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.

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

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

这篇关于我应该避免在Prolog中以及一般情况下进行尾递归吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！