这可以在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中进行尾递归吗？

回答

相关问题