Can this be made tail-recursive in Prolog?

2.1k views Asked by At

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.

1

There are 1 answers

4
gusbro On BEST ANSWER

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