这可以在 Prolog 中进行尾递归吗？

发布于 2024-12-11 12:46:47 字数 634 浏览 0 评论 0原文

我正在学习 Prolog，作为练习，我正在尝试一个简单的数据库，该数据库计算给定数字之前的所有数字的总和（即 0=0, 1=1, 2=3, 3=6, 4 =10，...）。很简单：

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 统一之前不能使用 PrevSum 的信息。代码>counting_sum(PrevNum, PrevSum)。这是正确的吗？有什么方法可以使这个尾递归吗？我正在使用 GNU Prolog 1.3.1（如果这有什么区别的话）。

PS 我对术语仍然犹豫不决。如果我错误地使用了这些术语，请告诉我。

原文

I'm learning Prolog, and as an exercise, I'm experimenting with a simple database that calculates the sum of all numbers up to the given number (i.e. 0=0, 1=1, 2=3, 3=6, 4=10, ...). Easy enough:

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

That blows up somewhere around counting_sum(150000, X). with a stack overflow. I understand that Prolog can do tail recursion, but if I move the recursive call to the end of the rule, I get

error(instantiation_error,(is)/2)

which I assume is telling me I can't use PrevSum before it's been unified with counting_sum(PrevNum, PrevSum). Is that correct, and is there any way to make this tail-recursive? I'm using GNU Prolog 1.3.1 if that makes any difference.

P.S. I'm still shaky on the terminology. Let me know if I used the terms incorrectly.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

尐籹人 2024-12-18 12:46:47

尝试这样的事情（使用累加器）：

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

Try something like this (use an accumulator):

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

回复收藏 0 原文

~没有更多了~