Next: Accumulating Lists, Up: Last Call Optimization [Contents][Index]

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 `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.

Send feedback on this subject.