Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 40 ยท Lists and Recursion

Recursion in Prolog: Base Cases, Ancestors, Peano Numbers

Learn how recursion works in Prolog with a base case and a recursive case: ancestor relations, factorial, Peano arithmetic, graph reachability and how to avoid infinite loops.

Prolog has no for or while. Repetition is done by recursion: a predicate that is defined in terms of itself. Because Prolog also searches with backtracking, recursive predicates are often shorter and more general than their counterparts in other languages. This lesson shows the pattern and the pitfalls, using family trees, numbers and graphs. The next lessons apply it to lists.

Prolog is read-only on this site. All runnable blocks use the Python mini-Prolog stand-in, which supports recursion, is, comparisons and \+.

The pattern: base case and recursive case

A recursive predicate has at least two clauses:

  1. A base case that is true without recursion (the stopping point).
  2. A recursive case that reduces the problem and calls the predicate again on the smaller problem.

Back to the family tree. You wanted ancestor/2 for any number of generations:

PROLOG
parent(abe, tom).
parent(tom, bob).
parent(bob, zed).

ancestor(X, Y) :- parent(X, Y).                  % base: a parent is an ancestor
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).  % step: parent of an ancestor

Read the second clause in words: X is an ancestor of Y if X is a parent of some Z, and Z is an ancestor of Y. Each recursive call moves one generation closer to Y, so the chain ends when Z is a direct parent of Y.

PROLOG
?- ancestor(abe, zed).
true.

?- ancestor(A, zed).
A = bob ;
A = abe ;
A = tom.

Trace ancestor(abe, zed). The first clause needs parent(abe, zed): no. The second clause: parent(abe, Z) gives Z = tom; then ancestor(tom, zed): first clause parent(tom, zed) fails; second: Z = bob, ancestor(bob, zed), first clause parent(bob, zed) succeeds. Three levels deep.

flowchart TD
    A["ancestor(abe, zed)"] --> B["parent(abe, tom)"]
    A --> C["ancestor(tom, zed)"]
    C --> D["parent(tom, bob)"]
    C --> E["ancestor(bob, zed)"]
    E --> F["parent(bob, zed): true"]

Each call to ancestor/2 peels off one generation.

Clause order and where the recursion goes

Put the base case first and make the recursive call the last goal (right recursion), after a goal that makes progress. The opposite, as seen in search trees, loops:

PROLOG
ancestor(X, Y) :- ancestor(X, Z), parent(Z, Y).   % left recursion: loops on failure

This version is logically correct but when it needs to backtrack it calls ancestor(X, Z) forever. The rule of thumb: the recursive call must be on a smaller problem, and not the first thing the clause does.

Recursion on numbers

Counting uses is. The factorial N! = N * (N-1)!, with 0! = 1:

PROLOG
factorial(0, 1).
factorial(N, F) :-
    N > 0,
    N1 is N - 1,
    factorial(N1, F1),
    F is N * F1.
PROLOG
?- factorial(5, F).
F = 120.

The guard N > 0 matters. Without it, factorial(0, F) would match both clauses; after the first answer, backtracking would try the second clause with N1 = -1, then -2, and so on forever. The test N > 0 (or a cut, in chapter 5) makes the two clauses mutually exclusive.

A caution: factorial(N, 120) does not work backwards, because N > 0 and is need bound numbers. Arithmetic predicates are one-way; to run backwards you need constraint programming (the CLP(FD) chapter).

Peano numbers: pure recursion

You can define numbers without arithmetic. Write zero as 0 and the successor of N as s(N): so 1 is s(0), 2 is s(s(0)). Addition then needs only two clauses:

PROLOG
add(0, Y, Y).
add(s(X), Y, s(Z)) :- add(X, Y, Z).
PROLOG
?- add(s(s(0)), s(0), R).
R = s(s(s(0))).

?- add(A, B, s(s(0))).
A = 0, B = s(s(0)) ;
A = s(0), B = s(0) ;
A = s(s(0)), B = 0.

The second query runs addition backwards: it finds all pairs that sum to 2, something is-based arithmetic cannot do. This is the "relations, not functions" idea from the first lesson. Real programs use built-in integers for speed, but Peano numbers show what pure Prolog looks like and how recursion follows the shape of the data: 0 and s(X) are the two shapes, and there is one clause per shape.

Recursion on graphs

Reachability in a directed graph is ancestor in disguise:

PROLOG
edge(a, b).
edge(b, c).
edge(c, d).

reach(X, Y) :- edge(X, Y).
reach(X, Y) :- edge(X, Z), reach(Z, Y).

This works on an acyclic graph. If you add edge(c, a)., the graph has a cycle and reach(a, X) can circle forever, because Prolog does not remember where it has been. The usual fix is a list of visited nodes:

PROLOG
reach(X, Y, _)       :- edge(X, Y).
reach(X, Y, Visited) :- edge(X, Z), \+ member(Z, Visited), reach(Z, Y, [Z | Visited]).

The query is reach(a, d, [a]). member/2 and lists are the subject of the next lessons; the point here is that termination is your responsibility.

Try it: ancestors, factorial and Peano

Python Recursive predicates (mini-Prolog stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last query shows addition running backwards. The stand-in prints answers in the same order that SWI-Prolog would.

Try it: cycles and the visited list

Python Graph with a cycle (mini-Prolog stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The visited version finds b, a, c and d and always terminates. The naive version either finishes or runs out of stack, depending on whether the search enters the cycle.

Common mistakes

  • No base case, or a base case after the recursive clause so it is never reached on failure.
  • A recursive step that does not reduce the problem.
  • Forgetting a guard so that clauses overlap and backtracking produces extra answers.
  • Using is backwards (5 is X + 1 raises an instantiation error).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What are the two parts of a typical recursive predicate?

    The base case stops the recursion; the recursive case reduces the problem and calls the predicate again.
  2. 2. Why does factorial need N > 0 in the second clause?

    Without it, factorial(0, F) would also match the recursive clause on backtracking and run away.
  3. 3. In add(s(X), Y, s(Z)) :- add(X, Y, Z)., what is s?

    s/1 is our own functor; Peano numbers are written 0, s(0), s(s(0)).
  4. 4. How do you prevent infinite loops on a graph with cycles?

    Prolog does not track visited nodes. You must keep that list yourself.

Summary

  • Recursion = base case + recursive case on a smaller problem; put the base case first.
  • Right recursion terminates where left recursion loops.
  • Guards keep clauses mutually exclusive.
  • Peano numbers show pure, reversible recursion; is-based arithmetic is one-way.
  • Cycles need a visited list; termination is your job.

Next: Lists: Head and Tail