PrologEZ
Data & computation · Lesson 20 of 43

Recursion

Base case, recursive case, and accumulators for speed.

Prolog has no loops. Repetition is recursion: a predicate defined in terms of itself, on a smaller problem. Every recursive definition needs two kinds of clause:

  • a base case that stops the recursion;
  • a recursive case that does a little work and calls itself on something smaller.

Here is length, written from scratch:

% my_length(List, N): N is the number of elements of List
my_length([], 0).                         % base case: the empty list has length 0
my_length([_|T], N) :-                    % recursive case:
    my_length(T, M),                      %   the tail has length M
    N is M + 1.                           %   so the whole list has M + 1
?- my_length([a, b, c, d], N)

The same pattern computes sums, maxima, copies, filters…

my_sum([], 0).
my_sum([H|T], S) :- my_sum(T, S0), S is S0 + H.

fact(0, 1).
fact(N, F) :- N > 0, N1 is N - 1, fact(N1, F1), F is N * F1.

countdown(0) :- write(liftoff), nl.
countdown(N) :- N > 0, write(N), nl, N1 is N - 1, countdown(N1).
?- my_sum([1, 2, 3, 4], S)
?- fact(10, F)
?- fact(30, F)
?- countdown(3)

Accumulators: carrying the answer along

my_sum has to remember a pending addition at each level. An accumulator passes the running total down instead, so that the recursive call is the last thing that happens. That's a tail call, and Prolog optimises it into a loop that uses constant stack space.

% sum_acc(List, Acc, Sum)
sum_acc([], Acc, Acc).
sum_acc([H|T], Acc, Sum) :- Acc1 is Acc + H, sum_acc(T, Acc1, Sum).
my_sum2(List, Sum) :- sum_acc(List, 0, Sum).

% counting to a million without growing the stack
count(N, N) :- !.
count(I, N) :- I1 is I + 1, count(I1, N).
?- my_sum2([1, 2, 3, 4], S)
?- count(0, 1000000)

Why accumulators matter: reversing a list

The obvious reverse appends one element at a time, which re-copies the list at every step, quadratic time. With an accumulator you build the answer in one pass:

slow_reverse([], []).
slow_reverse([H|T], R) :- slow_reverse(T, RT), append(RT, [H], R).

fast_reverse(L, R) :- rev(L, [], R).
rev([], Acc, Acc).
rev([H|T], Acc, R) :- rev(T, [H|Acc], R).
?- fast_reverse([1, 2, 3, 4], R)
?- numlist(1, 3000, _L), slow_reverse(_L, [First|_])
?- numlist(1, 3000, _L), fast_reverse(_L, [First|_])

Compare the timings shown at the bottom right of each result.

Two recursive calls: Fibonacci

Some definitions call themselves more than once. The naive Fibonacci recomputes the same values over and over:

fib(0, 0).
fib(1, 1).
fib(N, F) :-
    N > 1,
    A is N - 1, B is N - 2,
    fib(A, FA), fib(B, FB),
    F is FA + FB.
?- fib(10, F)
?- fib(24, F)

Try fib(27, F) and watch the time climb. The cure is memoisation, remembering answers, which you'll meet in the database lesson.

Exercise: Sum to N

Write sum_to(N, S): S is 1 + 2 + … + N. Make sum_to(0, S) give 0, and make sure each query has exactly one answer.

Exercise: Count occurrences

Write count(X, List, N): N is how many times X appears in List. For example count(a, [a, b, a, c, a], N) gives N = 3.