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 is not 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
the recursive call to
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
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
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
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