Recursion: a rule that calls itself

No loops, so rules repeat

Prolog has no loop statement. Instead a rule asks itself a smaller question, and the engine keeps asking until the smallest case is reached. That smallest case is a fact or a short rule called the base case, and it is the only thing that stops the descent.

The example rule countdown(N) prints N and then asks the same rule for one less. When the argument reaches zero the first clause runs instead, so nothing deeper is called and the printing is done.

A trace makes the descent visible. countdown(2) matches the second clause, prints 2, and calls countdown(1). That call prints 1 and asks for countdown(0), which matches the first clause and prints liftoff. Only then do the waiting calls finish, one after another, and the program returns to main. The output reads downward even though the calls finish upward.

Answers that come back out

A recursive rule can also build a value on the way back up. A factorial rule asks for the factorial of one less and multiplies that answer by N: the multiplications happen after the deepest call has returned, which is why the result is assembled from the inside out.

Two habits keep this readable. Put the clause that stops the descent first, and guard the arithmetic — a goal like N > 0 — so a bad argument fails instead of running away.

The factorial shows the other direction. fact(3, F) asks for fact(2, F0), which asks for fact(1, F1), which asks for fact(0, F2). The base case binds F2 to 1, then each waiting clause multiplies on the way back: 1 times 1, then 2 times 1, then 3 times 2. The answer is assembled after the deepest call returns, not before it starts.

The shape of every recursive rule

Every recursive rule in this chapter has the same three parts: a clause for the smallest case, a clause that makes the problem smaller, and a call to itself on that smaller problem. The engine does not know that the argument is shrinking; the guard and the arithmetic are what make the descent finite.

If M is N - 1 never reaches the base case — because the guard is missing, or because N is a decimal — the chain of calls grows until the engine runs out of room. Recursion can also build a result as it returns: the deepest call reaches the base case first, then each waiting clause uses that answer to compute its own, which is why the arithmetic after the recursive call sees a finished value.

A useful check is to run the rule with the smallest input first, then one step larger; if the second call never reaches the first, the base case or the guard is wrong.

Clause order is part of the program. If the general clause had no guard and came before the clause for zero, it would match zero as well, subtract one, and keep going into negative numbers. The base case would still exist but would never be reached. Put the stopping clause first, or guard the general clause so it cannot match the base case.

What the engine does

Each recursive call adds a frame to the engine’s stack, holding the goals still to be solved and the bindings made so far. The frames grow until the base case matches, then unwind as each waiting goal finishes. A rule that never reaches a base case keeps adding frames until the stack limit is hit and the engine reports a resource error.

A factorial, built from the inside out

% The result is built on the way back out.
fact(0, 1) :- !.
fact(N, F) :-
    N > 0,
    M is N - 1,
    fact(M, F0),
    F is N * F0.

main :-
    fact(5, F),
    write('5 factorial is '), write(F), nl.
:- initialization(main).

Try these next

• Write sum_to/2 for 1 to N and check it by hand for N equal to 4.
• Write power(Base, Exp, Result) with a base case for exponent zero.
• Add a guard to the countdown so countdown(-1) fails instead of looping.