Recursion & backtracking: the Prolog execution model

How Prolog actually runs a query

The Prolog interpreter does left-to-right, depth-first search with backtracking over Horn clauses. Given a goal list, it always selects the leftmost goal, scans the program top-to-bottom for the first clause whose head unifies, and replaces the goal with that clause's body (pushed onto the front of the goal list — so the goal list behaves like a stack, which is what makes the search depth-first). If a goal fails, the interpreter backtracks to the most recent choice point and tries the next matching clause, undoing the bindings it made along the way.

That single mechanism — unify, expand, backtrack — is the whole engine. Understanding it lets you predict the *order* in which Prolog finds solutions, which is exactly what hand-tracing questions test.

Recursion: base case + recursive step

Prolog has no loops; repetition is recursion. Every recursive predicate needs two parts, and the order you write them in matters:

1. A base case that terminates the recursion (and is usually listed *first*, so it is tried before the recursive clause).
2. A recursive step that reduces the problem toward the base case.

Worked example — factorial (the exam A3 predicate)

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

The first clause is the base case: fact(0, 1) asserts $0! = 1$. The second is the recursive step: to compute fact(N, F), require N > 0, decrement to N1, recursively get fact(N1, F1), then F is N * F1. (is forces arithmetic evaluation — plain = would only *unify* the unevaluated term N * F1, a classic beginner bug.)

Trace ?- fact(3, F). — note how the multiplications happen on the way back up, after the base case is hit:

fact(3, F)  -> 3 > 0, fact(2, F1), F is 3 * F1
  fact(2, F1) -> 2 > 0, fact(1, F2), F1 is 2 * F2
    fact(1, F2) -> 1 > 0, fact(0, F3), F2 is 1 * F3
      fact(0, F3) -> F3 = 1            (base case)
    F2 is 1 * 1 = 1
  F1 is 2 * 1 = 2
F is 3 * 2 = 6

The Python exercise below implements the identical base-case-plus-recursive-step structure so you internalise the discipline before writing it in Prolog under exam pressure.