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 (see
bas-eff-cut-mpd), 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.