Sum of the first n numbers in prolog

user3043278 picture user3043278 · Jan 9, 2014 · Viewed 20.8k times · Source

Hello can anyone help me compute the sum of the first n numbers. For example n=4 => sum = 10. So far I've wrote this

    predicates
  sum(integer,integer)
clauses

  sum(0,0).
   sum(N,R):-
        N1=N-1,
        sum(N1,R1),
        R=R1+N.

This one works but I need another implementation. I don't have any ideas how I could make this differen . Please help

Answer

Nicholas Carey picture Nicholas Carey · Jan 10, 2014

What @mbratch said.

What you're computing is a triangular number. If your homework is about triangular numbers and not about learning recursive thinking, you can simply compute it thus:

triangular_number(N,R) :- R is N * (N+1) / 2 .

If, as is more likely, you're learning recursive thought, try this:

 sum(N,R) :-    % to compute the triangular number n,
   sum(N,1,0,R) % - invoke the worker predicate with its counter and accumulator properly seeded
   .

 sum(0,_,R,R).     % when the count gets decremented to zero, we're done. Unify the accumulator with the result.
 sum(C,X,T,R) :-   % otherwise,
   C > 0 ,         % - assuming the count is greater than zero
   T1 is T+X ,     % - increment the accumulator
   X1 is X+1 ,     % - increment the current number
   C1 is C-1 ,     % - decrement the count
   sum(C1,X1,T1,R) % - recurse down
   .               % Easy!

Edited to add:

Or, if you prefer a count down approach:

 sum(N,R) :- sum(N,0,R).

 sum(0,R,R).       % when the count gets decremented to zero, we're done. Unify the accumulator with the result.
 sum(N,T,R) :-     % otherwise,
   N > 0 ,         % - assuming the count is greater than zero
   T1 is T+N ,     % - increment the accumulator
   N1 is N-1 ,     % - decrement the count
   sum(N1,T1,R)    % - recurse down
   .               % Easy!

Both of these are tail-recursive, meaning that the prolog compiler can turn them into iteration (google "tail recursion optimization" for details).

If you want to eliminate the accumulator, you need to do something like this:

sum(0,0).
sum(N,R) :-
  N > 0 ,
  N1 is N-1 ,
  sum(N1,R1) ,
  R is R1+N
  .

A little bit simpler, but each recursion consumes another stack frame: given a sufficiently large value for N, execution will fail with a stack overflow.