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

问题描述

为了好玩，我正在阅读Learn Prolog now"在线书籍.

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屋！