ASP-08 | Recursive Rules
Recursive rules allow ASP programs to build up complex relationships from simpler ones by having rules reference themselves, enabling elegant solutions to problems such as computing sequences and traversing hierarchical structures.Photo Credit: Rob Grzywinski
Recursive Rules
Up until now, we've worked with rules where the body references facts or other rules. But what if we want to define a rule that builds upon itself? This is where recursive rules come in — rules that reference their own head predicate in their body. This powerful concept allows us to express relationships that build up incrementally.Understanding Recursion in ASP
In imperative programming, recursion involves a function calling itself. In ASP, recursion means a rule using its own head predicate to define new facts. The key differences are:- We don't "call" anything — we define relationships
- We must provide a base case (anchor) that doesn't depend on recursion
- We must ensure the recursion terminates
Example: Computing Factorials
A factorial (n!) is the product of all positive integers less than or equal to n. For example three factorial is:3! = 3 · 2 · 1.0! = 11! = 1 · 0!2! = 2 · 1!3! = 3 · 2!... and so on.
We can express this relationship as n! = n · (n - 1)! for n > 0 . In ASP, it's always best to think of the value that you have as n and the next value as n + 1. In other words, we want our rule to relate the next value, n + 1, to a value that we already have, n. Rewriting the relationship in this way yields (n + 1)! = (n + 1) · n! for n > 0 where 0! = 1.The biggest challenge for imperative programmers at this point is to fight the urge to write a set of (imperative) instructions that tells the computer how to compute a factorial. In declarative programming, it is our job to describe the problem and its constraints rather than specify instructions as to how to solve the problem. So how do we describe the problem?We already did!
Let's pick a use case: n = 3; n! = 6.#const n = 3 .
Remember to think of predicates as relations. factorial/2 relates a number to its factorial. The first rule:factorial(0, 1) .
is the anchor that relates 0 to its factorial 0! = 1 — all other factorials can be built from this.The recursive rule relates a number (specifically the next number) to a factorial:factorial(N + 1, (N + 1) * F) ← factorial(N, F), N < n .
The body of this rule simply defines two variables, N which the current number and F which is N factorial, and a condition that ensures that the recursion stops. The head of the second rule simply states the definition of the next factorial given n.If this is the first time that you've seen this type of relation, it can be a lot to take in. So let's break it down:- When you have a recursive rule, make sure that you look at the anchor rule (2) since it helps you get a leg to stand on; it's what the rule builds up from.
- Remember how rules are read: "If body is in the answer set then head is in the answer set". This means that rules should be read from right to left; always start understanding a rule from its body. We know that we have
factorial(0, 1) as our base. The first term is the number and the second term is that number's factorial. - We know how to get the next factorial (n + 1) given a factorial (n!): (n + 1)! = (n + 1) · n! So if we wrote
factorial(N, F), how would we write the next factorial in terms of N and F? factorial(N + 1, (N + 1) * F) - We just need to make sure that our program doesn't recurse forever and that's where the
N < n comes in. That's it!
All that's left to do is to "ask" our program for the results. We do this by specifying what we want to know from our relation and extracting what the related value is.factorial(F) ← factorial(n, F) .
Example: Genealogy
Let's revisit our genealogy example but push it further by adding more generations. We'll expand beyond just parents to include grandparents:mother((janie ; pete ; tommy ; zuzu), mary) .
father((janie ; pete ; tommy ; zuzu), george) .
mother(mary, ruth) . % Mary's mother
father(mary, henry) . % Mary's father
mother(george, sarah) . % George's mother
father(george, william) . % George's father
We already know how to express the parent relationship:parent(C, P) ← mother(C, P) .
parent(C, P) ← father(C, P) .
But here's where things get interesting. How do we express "ancestor"? An ancestor is either:- A parent (directly), or
- A parent of someone who is already an ancestor
This naturally leads to recursion!ancestor(X, Y) ← parent(X, Y) . % Base case
ancestor(X, Z) ← parent(X, Y), ancestor(Y, Z) . % Recursive case
The first rule says "if Y is X's parent, then Y is X's ancestor" — that's our base case. The second rule is where the magic happens: "if Y is X's parent and Z is Y's ancestor, then Z is also X's ancestor". This recursive definition captures the entire ancestral chain!Now we can ask questions: who are Pete's grandparents?grandparent(X) ← parent(P, X), parent(pete, P) .
{| grandparent/1 |
|---|
| henry |
| ruth |
| sarah |
| william |
} petes_ancestors(X) ← ancestor(pete, X) .
{| petes_ancestors/1 |
|---|
| george |
| henry |
| mary |
| ruth |
| sarah |
| william |
} A Note on Cycles
If you're familiar with SQL, you may have noticed that recursive queries require explicit cycle prevention. For example, when finding ancestors in SQL, you need to explicitly track the path taken to avoid infinite loops such as:pete → mary → ruth → mary → ruth → …WITH RECURSIVE ancestors AS (
-- Base case: direct parents are ancestors
SELECT child AS descendant
, parent
, ARRAY[child, parent] as path -- Track the path
FROM parent_relation
WHERE child = 'pete'
UNION ALL
-- Recursive case: only follow paths we haven't seen
SELECT ancestors.descendant
, parent_relation.parent
, ARRAY_CONCAT(ancestors.path, [parent_relation.parent]) -- Extend the path
FROM Ancestors
JOIN parent_relation
ON parent_relation.child = ancestors.parent
WHERE NOT parent_relation.parent IN UNNEST(ancestors.path) -- Prevent cycles
)
One of ASP's elegant features is that it handles cycles automatically through its stable model semantics. Our ancestor rule:ancestor(X, Z) ← parent(X, Y), ancestor(Y, Z) .
just works with no explicit cycle prevention needed. The solver builds answer sets systematically from facts and rules, ensuring only valid derivations are included. This "free" cycle handling is one of the key advantages of using ASP for recursive relationships.
Key Points About Recursive Rules
When working with recursive rules in ASP, keep these important principles in mind:- Base Case Required: Always provide a non-recursive rule (anchor) that establishes the foundation for your recursion. Without it, there's nothing for the recursive rules to build upon.
- Termination Important: Ensure your recursive rules have conditions that will eventually stop the recursion. The solver needs to be able to find all stable models in finite time.
- Think Declaratively: Focus on describing relationships rather than steps. Don't try to translate imperative recursive algorithms directly into ASP.
- Build Up: It often helps to think about how to derive the next case from what you already have, rather than how to break down a problem into smaller pieces.
The power of recursive rules lies in their ability to express complex relationships succinctly. While they may take some time to get comfortable with, they're an essential tool in the ASP programmer's toolkit.
