Recursive Rules in Prolog
What you'll learn: How to define recursive logical relationships in Prolog to express complex patterns like ancestorship, graph traversal, and list processing.
The Core Idea
Prolog shines when expressing recursive relationships—rules that refer to themselves to capture patterns that repeat or "unfold." Just as mathematical recursion breaks problems into smaller instances, recursive Prolog rules build complex queries from simpler base cases.
Think of ancestry: your ancestor is either your parent (base case) or your parent's ancestor (recursive case). In Prolog, you express this directly as logical rules.
Anatomy of a Recursive Rule
A typical recursive rule has two parts:
- Base case: The simplest facts that terminate recursion
- Recursive case: A rule that refers back to itself with modified arguments
Example: Ancestor Relationship
% Base case: parent is an ancestor
ancestor(X, Y) :- parent(X, Y).
% Recursive case: ancestor of parent is ancestor
ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).
When you query ancestor(alice, bob), Prolog tries the base case first, then explores the recursive rule through backtracking, building chains of parenthood.
Example: List Operations
% Check if X is in list
member(X, [X|_]). % Base: X is the head
member(X, [_|Tail]) :- member(X, Tail). % Recursive: check tail
Each recursive call peels off one element, matching the pattern we saw with Lists in Prolog and leveraging Backtracking to explore alternatives.
Why This Matters
Recursive rules transform declarative facts into powerful queries. You describe what relationships mean—Prolog figures out how to find them through unification and backtracking.
Key Takeaway: Recursive rules in Prolog express repeating logical patterns with base and recursive cases, enabling elegant definitions of ancestry, paths, membership, and other inductive relationships.