​
Recursion

A Vadalog program or ontology is recursive if the dependency graph implied by the rules is cyclical. The simplest form of recursion is that in which the head of a rule also appears in the body (self-recursive rules). Recursion is particularly powerful as it allows for inference based on previously inferred results. In self-recursive rules, in case of bodies with two atoms, we distinguish between:
  1. left recursion, where the recursive atom is the left-most;
  2. right recursion, where the recursive atom is the right-most.
edge(1, 2).
edge(2, 3).
edge(1, 4).
edge(4, 5).
path(X, Y) <- edge(X, Y).
path(X, Z) <- path(Y, Z), edge(X, Y).
@output("path").
The expected results: 
path(1, 3).
path(1, 2).
path(1, 5).
path(2, 3).
path(1, 4).
path(4, 5).
This shows reachability in graphs using left recursion. For more complex examples, see Recursion patterns and Graph Analytics.