這可以在Prolog中進行尾遞歸嗎？

我正在學習Prolog，作爲一個練習，我正在試驗一個簡單的數據庫，它可以計算所有數字之和，直到給定的數字（即0 = 0,1 = 1,2 = 3，3 = 6 ，4 = 10，...）。足夠簡單：這可以在Prolog中進行尾遞歸嗎？

counting_sum(0, 0). 
counting_sum(Num, Sum) :- Num > 0, PrevNum is Num - 1, 
    counting_sum(PrevNum, PrevSum), Sum is Num + PrevSum.

這會在堆棧溢出時在counting_sum(150000, X).附近爆炸。據我所知，Prolog的可以做尾遞歸，但如果我移動遞歸調用統治的結束，我得到

error(instantiation_error,(is)/2)

我以爲是告訴我，我不能用PrevSum之前它被統一爲counting_sum(PrevNum, PrevSum) 。這是否正確，是否有任何方法可以做出這種尾遞歸？我使用的是GNU Prolog 1.3.1，如果這有什麼不同。

P.S.我仍然對術語感到不安。如果我錯誤地使用了這些術語，請告訴我。

來源

2011-10-22 Ryan Stewart

你說得對有關實例錯誤的原因。 –

嘗試這樣的事情（使用蓄電池）：

counting_sum(Count, Sum):- 
    counting_sum(Count, 0, Sum). 

counting_sum(0, Sum, Sum). 
counting_sum(Num, PrevSum, Sum):- Num > 0, PrevNum is Num - 1, 
    NextSum is PrevSum + Num, 
    counting_sum(PrevNum, NextSum, Sum).

來源

2011-10-22 23:09:04 gusbro

謝謝。我沒有遇到累加器。它[看起來像一個有用的成語]（http://www.lix.polytechnique.fr/~liberti/public/computing/prog/prolog/prolog-tutorial.html#iteration）。在閱讀並理解了累加器的內容後，我可以使用它來編寫一個新的實現，然後根據您的代碼進行檢查。我想出了同樣的事情。問題：我仍然在'counting_sum（350000，X）處得到堆棧溢出。「任何想法爲什麼？ –

這很奇怪。我試着用'3500000'（十倍於你的數字）提供給SWI的代碼，並且它很容易處理。 – gusbro

我在猜測，但GNU Prolog可能不會在解釋模式下進行尾部優化（但是SWI Prolog會）。 @RyanStewart：如何確認您是使用編譯的gprolog可執行文件，還是僅使用解釋器？ – hardmath

這可以在Prolog中進行尾遞歸嗎？

回答

相關問題