我正在通過「Learn Prolog now」在線書籍尋找樂趣。我應該避免使用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).
簡短回答：尾遞歸是可取的，但不要過分強調它。
您的原始程序是作爲您可以在Prolog中獲得的尾遞歸。但還有更重要的問題：正確性和終止。實際上，許多實現都願意犧牲他們認爲更重要的其他屬性的尾遞歸。例如steadfastness。
但您的嘗試優化有一點。至少從歷史的角度來看。
早在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的第一個版本應該會導致效率較低的代碼。它也更具可讀性，所以我看不出爲什麼它應該是避免它的好實踐。
在更復雜的示例中，編譯器可能無法將代碼自動傳輸到尾遞歸。那麼將其重寫爲優化可能是合理的，但只有在真正有必要的時候纔可以。
那麼，如何實現一個工作尾遞歸版本addone？這可能是在欺騙，但假設reverse與尾遞歸（例如，見here）來實現，那麼它可以用來解決您的問題：
它的極端笨拙，雖然。 :-)
順便說一句，我找不到一個更簡單的解決方案。這可能是因爲與Haskell中的foldr相同的原因通常沒有使用尾遞歸來定義。
+1，因爲只有你注意到OP的accAddOne是錯誤的。 – day
您的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尾遞歸：遞歸調用是最後一個，和沒有選擇點。
O.P.說：
但我已閱讀，這是更好地避免[尾巴]遞歸出於性能的考慮。 這是真的嗎？總是使用尾遞歸是否被認爲是「良好實踐」？ 值得努力使用累加器來養成良好的習慣嗎？
這是一個相當直接的優化，將尾遞歸構造轉換爲迭代（一個循環）。由於tail（遞歸）調用是最後一件事情，因此可以在遞歸調用中重用棧幀，通過簡單地跳轉到謂詞/函數/方法的開始，爲所有意圖和目的製作循環，一個循環/子程序。因此，尾遞歸謂詞不會溢出堆棧。尾遞歸構造，應用了優化，具有以下好處：
可能的缺點？
當語言標準要求尾遞歸優化時，這當然不是問題。
引述維基百科：
尾調用是顯著，因爲它們可以在不增加 一個新的堆棧幀調用棧來實現。當前程序 的大部分幀不再需要，可以用尾部呼叫幀 進行適當修改（類似於進程的重疊，但對於功能 調用）。程序然後可以跳轉到被調用的子程序。生成此類代碼 而不是標準呼叫序列稱爲尾呼叫消除，或尾呼叫優化。
參見：
我永遠無法理解爲什麼更多的語言不實行尾遞歸優化
由於邏輯變量和非確定性，Prolog中的情況比其他語言複雜得多。事實上，它是Prolog機器中複雜性的主要來源：在WAM中，它導致了一個非常複雜的（和聰明的）可變分類方案，這往往導致實現中遺漏了其一部分。 ZIP需要對相關變量進行昂貴的動態掃描，並且在GC期間需要一些開銷。 – false
' addone'已經完全可以通過尾巴優化。它是[tail遞歸*「modulo cons」*]（https://en.wikipedia.org/wiki/Tail_call#Tail_recursion_modulo_cons），並且Prolog確實有這種優化 - 新的單元格[Y | Ys]是分配* first *與其中的兩個「洞」（兩個尚未實例化的logvars，'Y'和'Ys'），然後'Y'在規則體內實例化（通過'is/2'），然後* *遞歸調用實例化邏輯變量'Ys'。因此不需要從遞歸調用返回到這個規則的主體。 –
LPN！現在通過實例展示了不同之處。就我所知，Prolog是尾部遞歸優化的，因此它是可取的，因爲它通過不退後有效地將N步變爲N/2。 LPN：http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse20第5.3章，2018年1月。 –