Prolog/递归规则
本节介绍如何递归使用规则。也就是说，让规则引用自身。这是 Prolog 中最重要的机制之一，但一开始可能很难使用。
考虑以下程序。
parent(david, john).
parent(jim, david).
parent(steve, jim).
parent(nathan, steve).
grandparent(A, B) :- parent(A, X), parent(X, B).
它展示了家庭树中的男性血统，并用规则定义了某人是某人的祖父母（如果他是那个人父母的父母）。
如果我们想定义某人是某人的祖先呢？也就是说，父母、祖父母、曾祖父母等等。如果我们为所有这些情况编写规则，我们可以为此特定血统定义 ancestor(A,B)
ancestor(A,B) :- parent(A, B).
ancestor(A,B) :- parent(A, X), parent(X, B).
ancestor(A,B) :- parent(A, X), parent(X, Y), parent(Y, B).
ancestor(A,B) :- parent(A, X), parent(X, Y), parent(Y, Z), parent(Z,B).
显然这不是正确的方法。它不优雅，工作量很大，最重要的是，它仍然没有正确地定义 ancestor。这可能适用于一个有四代人的血统，但如果我们想在程序中添加第五个父母，我们也需要添加 ancestor 的新行。我们需要一个适用于任何父母血统的 ancestor 定义，无论多长。
为了实现这一点，我们需要思考祖先的定义。首先，人 P 是人 C 的祖先，如果 P 是 C 的父母。此外，我们可以说人 A 是人 C 的祖先，如果人 A 是 C 的祖先的父母。这听起来不太有用，因为我们在自己的定义中使用了 ancestor 这个词，但与第一个陈述一起使用，它就变成了一个完整的定义。
例如，如果我们要问自己 Steve 是否是 John 的祖先，我们会查看定义。Steve 当然不是 John 的父母，所以这并不适用。Steve 是 John 的祖先的父母吗？Steve 是 Jim 的父母，所以问题变成了，Jim 是 John 的祖先吗？Jim 是 David 的父母，所以 David 是 John 的祖先吗？在这里我们可以使用第一个定义，因为 David 是 John 的父母。
在 prolog 中，定义看起来像这样
ancestor(A, B) :- parent(A, B).
ancestor(A, B) :- parent(A, X), ancestor(X, B).
第二个规则是递归的；它使用 ancestor 来定义 ancestor。第一个规则被称为停止谓词，因为它停止谓词调用自身。
当遇到查询 ?- ancestor(steve,john). 时，prolog 将首先尝试定义的第一行，但无法将 parent(steve, john) 与数据库中的任何一行统一。它将尝试第二行并得出子目标 parent(steve, X) 和 ancestor(X, B)。它可以将 parent(steve, X) 与 parent(steve, jim) 统一，因此 prolog 剩下子目标 ancestor(jim, john)。它将继续这样做，直到剩下子目标 ancestor(david, john)，它使用定义的第一行是正确的，因为 parent(david, john) 是正确的。
Prolog 非常擅长使用递归规则。它可以非常容易地找到 John 的所有祖先
?- ancestor(X, john).
X = david ;
X = jim ;
X = steve ;
X = nathan ;
No
或所有 Nathan 是祖先的人
?- ancestor(nathan, X).
X = steve ;
X = jim ;
X = david ;
X = john ;
No
使用递归规则并非没有风险，它会导致各种循环，这通常会导致堆栈溢出，意味着 prolog 已耗尽内存。编写递归规则时，应始终牢记以下准则。
- 从你的停止谓词开始。
- 始终将非递归谓词放在递归谓词之前。如果你从递归谓词开始，prolog 将尝试在看到它是否可以停止递归之前搜索“更深”。在上面的示例中，它实际上没有区别，但你的程序并不总是那么干净和直接。
- 避免在左侧递归
- 编写递归规则时，如果可能的话，将递归规则放在右侧。例如，使用
a :- b, a.
- 而不是
a :- a, b.
- 这与上一条准则相同，让 prolog 首先评估非递归目标。如果你在评估其他子目标之前递归，prolog 可能会陷入无限递归中，或者做很多不必要的工作。有时有必要将递归元素放在左侧，但不要这样做，除非你知道你为什么要这样做。
- 递归函数的经典例子是阶乘函数。您可以在 数学、函数和等式 部分看到它是如何实现的。在大多数编程语言中，您可能会通过编写一个 fact() 函数来学习递归，该函数以正整数作为输入，并返回一个正整数。在 Prolog 中，由于我们通常使用谓词而不是函数，因此我们将定义一个谓词 fact(X,Y)，它等效于语句“X 的阶乘是 Y”。然后，例如，为了找到 7 的阶乘，我们将使用查询 ?- fact(7,X)。然后 Prolog 将告诉我们：X=5040。
- 可以轻松递归定义的一件事是列表。在这种情况下，我们将列表视为按一定顺序排列的一组东西（元素）。要递归定义这一点，我们将声明列表是一个单一元素，后面跟着一个列表。为了结束递归，我们需要第二条语句，它说列表是由一个元素组成的东西。这两条定义一起准确地定义了任何是列表的东西。
- 列表实际上是 prolog 程序中非常常见的结构，它们以递归的方式使用。下一章将解释如何使用它们。