Recursion

Recursion is Prolog's only looping mechanism.

10.1 Structure of a recursive predicate

Base case(s) — stop condition.

Recursive case(s) — reduce the problem and call itself.

% Natural numbers in Peano notation
nat(0).
nat(s(N)) :- nat(N).

plus_peano(0, Y, Y).
plus_peano(s(X), Y, s(Z)) :- plus_peano(X, Y, Z).

?- plus_peano(s(s(0)), s(0), R).    % R = s(s(s(0)))
?- plus_peano(X, Y, s(s(0))).       % enumerates all splits — reversible!

10.2 Classic examples

% Counting down
countdown(0) :- write('Liftoff!'), nl.
countdown(N) :- N > 0, write(N), nl, N1 is N - 1, countdown(N1).

% Fibonacci
fib(0, 0).
fib(1, 1).
fib(N, F) :- N > 1, N1 is N-1, N2 is N-2, fib(N1, F1), fib(N2, F2), F is F1 + F2.

% Power
power(_, 0, 1).
power(B, E, R) :- E > 0, E1 is E - 1, power(B, E1, R1), R is B * R1.

% GCD (Euclid)
gcd(X, 0, X) :- X > 0.
gcd(X, Y, G) :- Y > 0, Z is X mod Y, gcd(Y, Z, G).

% Ancestor (transitive closure)
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

% Path in a graph
edge(a, b). edge(b, c). edge(c, d). edge(a, d).
path(X, Y) :- edge(X, Y).
path(X, Y) :- edge(X, Z), path(Z, Y).

10.3 Termination tips

Put base cases first.

Ensure each recursive call works on a smaller problem.

Avoid left recursion (or use tabling).

In graphs with cycles, track visited nodes:

path(X, Y, Path) :- path(X, Y, [X], Rev), reverse(Rev, Path).
path(X, Y, Visited, [Y|Visited]) :- edge(X, Y), \+ memberchk(Y, Visited).
path(X, Y, Visited, Path) :-
    edge(X, Z), Z \== Y, \+ memberchk(Z, Visited),
    path(Z, Y, [Z|Visited], Path).