Prolog recursion simple explanation

Question

I have the following recursion rules which returns the sum of a number, but I don't know how does it return the sum:

sum(1,1).
sum(A,Result) :-
    A > 0,
    Ax is A - 1,
    sum(Ax,Bx),
    Result is A + Bx.

now when you execute the following command in Prolog:

sum(3,X).

the answer will be 5, but as I look into the rules, I can't see how does these rules return values and sum the. How is the value of Bx is calculated ?

in C this would be sum(a){ if (a>0) {a + sum(a-1);} }. Prolog makes the evaluation order much clearer, more explicit, less "mysterious". — Will Ness

lurker lurker · Accepted Answer · 2013-12-24T22:12:58

sum(3,X). actually gives a result of X = 6. This predicate (sum(N, X)) computes the sum of integers from 1 to N giving X:

X = 1 + 2 + 3 + ... + N.

So it is the sum of the integers from 1 to N.

sum(1,1) says the sum of 1 by itself is just 1. This is true. :)

The second clause should compute the sum for A > 1, but it's actually not totally properly written. It says A > 0 which is ignoring the fact that the first clause already takes care of the case for 1. I would have written it with A > 1. It will work as is, but be a little less efficient.

sum(A,Result) :-
    A > 0,
    Ax is A - 1, 
    sum(Ax, Bx),       % Recursively find the sum of integers 1 to A-1
                       % Instantiate Bx with that sum
    Result is A + Bx.  % Result is A plus sum (in Bx) from 1 to A-1

This clause recursively says that the sum of integers from 1 to A is Result. That Result is the sum of A and the sum of integers from 1 to A-1 (which is the value Ax is unified to). The Bx is the intermediate sum of integers 1 through Ax (A-1). When it computes the sum(Ax, Bx), the value of Ax is 1 less than A. It will continue calling this second clause recursively until the first parameter goes down to 1, at which point the first clause will provide the value for the sum, and the recursion will unravel from there, summing 1, 2, 3, ...

EDIT: More Details on the Recursion

Let's look at sum(3,X) as an example.

sum(3,X) doesn't match sum(1,1). so that clause is skipped and Prolog looks at sum(A, Result). Prolog matches this by instantiating A as 3 and Result as X and steps through the statements making up the clause:

% SEQUENCE 1
% sum(A, Result) query issued with A = 3

3 > 1,         % true
Ax is 3 - 1,   % Ax is instantiated as the value 2
sum(2, Bx),    % recursive call to `sum`, `Ax` has the value of 2
Result is 3 + Bx.  % this statement is awaiting the result of `sum` above

At this point, Prolog suspends computing Result is A + Bx in order to make the recursive call. For the recursive call, Prolog can't match sum(Ax, Bx) to sum(1,1) because Ax is instantiated as 2. So it goes on to the next clause, sum(A, Result) and can match if it instantiates A as 2 and Result as Bx (remember, this is a new call to this clause, so these values for A and Result are a different copy than the ones we "suspended" above). Now Prolog goes through sum(A, Result) statements again, this time with the new values:

% SEQUENCE 2
% sum(A, Result) query issued with A = 2

2 > 0,         % true
Ax is 2 - 1,   % Ax is instantiated to the value 1
sum(1, Bx),    % recursive call to `sum`, `Ax` has the value of 1
Result is 2 + Bx.  % this statement is awaiting the result of `sum` above

Now Prolog has sum(1, Bx) (Ax is instantiated with 1). This will match sum(1,1) and instantiate Bx with 1 in the last query to sum above in SEQUENCE 2. That means Prolog will complete the sequence:

Result is 2 + 1.   % `A` is 2 and `Bx` is 1, so `Result` is 3

Now that this result is complete, the recursive query to sum in the prior execution in SEQUENCE 1 will complete in a similar fashion. In this case, it is instantiated Bx with 3:

Result is 3 + 3.  % `A` is 3 and `Bx` is 3 (from the SEQUENCE 2 query)
                  % so `Result` is 6

And finally, the original query, sum(3, X) completes, where X is instantiated with the result of 6 and you get:

X = 6.

This isn't a perfect explanation of how the recursion works, and there are some texts around with graphical representations that help. But I hope this provides some insight into how it operates.

Prolog recursion simple explanation

1 Answers