Course contentsShow
← Computer Science
Lesson 2162 of 2,87248. Programming ParadigmsFree lesson

Recursive Rules in Prolog

Defining recursive relationships like ancestor, path, and list operations using logical rules.

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:

  1. Base case: The simplest facts that terminate recursion
  2. 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.