Accumulating Parameters

To take best advantage of this feature, make sure that goals in recursive predicates are determinate, and whenever possible put the recursive call at the end of the predicate.

This isn't always possible, but often can be done through the use of accumulating parameters. An accumulating parameter is an added argument to a predicate that builds up the result as computation proceeds. For example, in our factorial example, the last goal in the body of the recursive case is is/2, not the recursive call to fac/2.

     fac(N, X) :-
         (   N > 0 ->
                 N1 is N - 1,
                 fac(N1, Y),
                 X is N * Y
         ;   N =:= 0 ->
                 X = 1
         ).
     

This can be corrected by adding another argument to fac/2 to accumulate the factorial.

     fac(N, X) :- fac(N, 1, X).
     
     %  fac(+N, +M, -X)
     %  X is M * the factorial of N.
     
     fac(N, M, X) :-
         (   N > 0 ->
                 N1 is N - 1,
                 M1 is N * M,
                 fac(N1, M1, X)
         ;   N =:= 0 ->
                 X = M
         ).
     

Here, we do the multiplication before calling fac/3 recursively. Note that we supply the base case, 1, at the start of the computation, and that we are multiplying by decreasing numbers. In the earlier version, fac/2, we multiply after the recursive call, and so we multiply by increasing numbers. Effectively, the new version builds the result backwards. This is correct because multiplication is associative.