递归¶

QL 对递归提供了强有力的支持。QL 中的谓词被称为递归谓词，如果它直接或间接地依赖于自身。

为了评估递归谓词，QL 编译器会找到递归的最小不动点。具体来说，它从空值集合开始，通过反复应用谓词来查找新值，直到值集合不再发生变化。此集合即为最小不动点，因此也是评估的结果。类似地，QL 查询的结果是查询中引用的谓词的最小不动点。

在某些情况下，您也可以递归地使用聚合。有关更多信息，请参阅“单调聚合”。

递归谓词的示例¶

以下是一些 QL 中递归谓词的示例

以下查询使用谓词 getANumber() 列出从 0 到 100（含）的所有整数

int getANumber() {
  result = 0
  or
  result <= 100 and result = getANumber() + 1
}

select getANumber()

谓词 getANumber() 评估为包含 0 以及任何比集合中已有的数字大一的整数（最多到 100）的集合。

谓词可以相互递归，也就是说，您可以有一个依赖于彼此的谓词循环。例如，以下是一个使用偶数计算到 100 的 QL 查询

int getAnEven() {
  result = 0
  or
  result <= 100 and result = getAnOdd() + 1
}

int getAnOdd() {
  result = getAnEven() + 1
}

select getAnEven()

此查询的结果是从 0 到 100 的偶数。您可以将 select getAnEven() 替换为 select getAnOdd() 以列出从 1 到 101 的奇数。

谓词的传递闭包是一个递归谓词，其结果通过反复应用原始谓词获得。

具体来说，原始谓词必须有两个参数（可能包括 this 或 result 值），并且这些参数必须具有兼容类型。

由于传递闭包是递归的一种常见形式，因此 QL 有两个有用的缩写

传递闭包 +

要将谓词应用一次或多次，请在谓词名称后附加 +。

例如，假设您有一个名为 Person 的类，它具有一个成员谓词 getAParent()。那么 p.getAParent() 将返回 p 的任何父代。传递闭包 p.getAParent+() 将返回 p 的父代、p 的父代的父代，等等。

使用此 + 符号通常比显式定义递归谓词更简单。在这种情况下，显式定义可能如下所示
```
Person getAnAncestor() {
  result = this.getAParent()
  or
  result = this.getAParent().getAnAncestor()
}
```
谓词 getAnAncestor() 等效于 getAParent+()。
自反传递闭包 *

这与上面的传递闭包运算符类似，只是您可以使用它将谓词应用于自身零次或多次。

例如，p.getAParent*() 的结果是 p 的祖先（如上所述），或者 p 本身。

在这种情况下，显式定义如下所示
```
Person getAnAncestor2() {
  result = this
  or
  result = this.getAParent().getAnAncestor2()
}
```
谓词 getAnAncestor2() 等效于 getAParent*()。

虽然 QL 旨在用于查询递归数据，但递归定义有时难以正确实现。如果递归定义包含错误，那么通常您会得到没有结果或编译器错误。

以下示例说明导致无效递归的常见错误

首先，有效的递归定义必须有一个起点或基本情况。如果递归谓词评估为空值集合，则通常存在问题。

例如，您可能尝试定义谓词 getAnAncestor()（来自上面的示例）如下

Person getAnAncestor() {
  result = this.getAParent().getAnAncestor()
}

在这种情况下，QL 编译器会给出错误，指出这是一个空递归调用。

由于 getAnAncestor() 最初被假定为空，因此无法添加新值。谓词需要一个递归起点，例如

Person getAnAncestor() {
  result = this.getAParent()
  or
  result = this.getAParent().getAnAncestor()
}

有效的递归谓词还必须是单调的。这意味着（相互）递归仅在偶数个否定下才允许。

从直观上讲，这可以防止“说谎者悖论”情况，在这种情况下，递归没有解决方案。例如

predicate isParadox() {
  not isParadox()
}

根据此定义，谓词 isParadox() 恰好在它不成立时成立。这是不可能的，因此递归没有固定点解决方案。

如果递归出现在偶数个否定下，那么这不是问题。例如，考虑以下（有点可怕的）类 Person 的成员谓词

predicate isExtinct() {
  this.isDead() and
  not exists(Person descendant | descendant.getAParent+() = this |
    not descendant.isExtinct()
  )
}

p.isExtinct() 成立，如果 p 及其所有后代都已死亡。

对 isExtinct() 的递归调用嵌套在偶数个否定中，因此这是一个有效的定义。实际上，您可以将定义的第二部分改写如下

forall(Person descendant | descendant.getAParent+() = this |
  descendant.isExtinct()
)