递归

Created: November-22, 2018

Prolog 没有迭代，但所有迭代都可以使用递归重写。当谓词包含引用自身的目标时，将出现递归。在 Prolog 中编写这样的谓词时，标准的递归模式总是至少包含两部分：

Base（非递归）子句 ：通常，基本情况规则将代表你尝试解决的问题的最小可能示例 - 没有成员的列表，或者只有一个成员，或者如果你’正在使用树结构，它可能处理一个空树，或者只有一个节点的树，等等。它非递归地描述了递归过程的基础。
递归（continue）子句 ：包含任何必需的逻辑，包括对自身的调用，继续递归。

作为一个例子，我们将定义众所周知的谓词 append/3。以声明方式查看，当列表 L3 是附加列表 L1 和 L2 的结果时，append(L1,L2,L3) 成立。当我们试图找出谓词的声明性含义时，我们试图描述谓词所持有的解决方案。这里的困难在于试图避免任何逐步重复出现的细节，同时仍然牢记谓词应该表现出的程序行为。

% Base case
append([],L,L).

% Recursive clause
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

基本情况以声明方式声明“附加到空列表的任何 L 是 L”，请注意，这并不表示 L 是空的 - 甚至不是列表（请记住，在 Prolog 中，所有内容都归结为术语）：

?- append(X,some_term(a,b),Z).
X = [],
Z = some_term(a, b).

为了描述递归规则，虽然 Prolog 从左到右执行规则，但是我们先省略头部并首先查看正文 - 从右到左阅读规则：

    append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

现在我们说，如果身体持有：“假设 append(L1,L2,L3) 持有”

    append([X|L1],L2,[X|L3]) :-  append(L1,L2,L3).

头脑也是如此：“那么 append([X|L1],L2,[X|L3])”

用简单的英语，这只是转换为：

假设 L3 是 L1 和 L2 的串联，那么[X 后跟 L3]也是[X 后跟 L1]和 L2 的串联。

在一个实际例子中：

“假设[1,2,3]是[1]和[2,3]的串联，那么[a，1,2,3]也是[a，1]和[2,3]的串联。 ”

现在让我们看一些查询：

最初使用最常见的查询测试谓词而不是为其提供特定的场景测试用例总是一个好主意。想一想：由于 Prolog 的统一，我们不需要提供测试数据，我们只需提供自由变量！

?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;                                   % Answer #1
L1 = [_G1162],
L3 = [_G1162|L2] ;                          % Answer #2
L1 = [_G1162, _G1168],
L3 = [_G1162, _G1168|L2] ;                  % Answer #3
L1 = [_G1162, _G1168, _G1174],
L3 = [_G1162, _G1168, _G1174|L2] ;          % Answer #4
...

让我们用字母替换自由变量 _G1162-like 表示法以获得更好的概述：

?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;                                   % Answer #1
L1 = [_A],
L3 = [_A|L2] ;                              % Answer #2
L1 = [_A, _B],
L3 = [_A, _B|L2] ;                          % Answer #3
L1 = [_A, _B, _C],
L3 = [_A, _B, _C|L2] ;                      % Answer #4
...

在第一个答案中，基本案例是模式匹配的，Prolog 将 L1 实例化为空列表并统一 L2 和 L3，证明 L3 是空列表和 L2 的串联。

在答案#2，通过按时间顺序回溯，递归子句发挥作用，Prolog 试图证明 L1 头部中与 L2 连接的某个元素是 L3，其列表头中具有相同的元素。为此，一个新的自由变量 _A 与 L1 的头部统一，L3 被证明现在是 [_A|L2]。

现在使用 L1 = [_A] 进行新的递归调用。再一次，Prolog 试图证明放在 L1 头部的一些元素与 L2 连接的是 L3，头部中有相同的元素。请注意，_A 已经是 L1 的头部，它完全符合规则，所以现在，通过递归，Prolog 将 _A 放在一个新的自由变量前面，我们得到 L1 = [_A,_B] 和 L3 = [_A,_B|L2]

我们清楚地看到递归模式重复自身并且可以很容易地看到，例如，递归中的第 100 步的结果将如下所示：

L1 = [X1,X2,..,X99],
L3 = [X1,X2,..,X99|L2]

注意：正如典型的 Prolog 代码一样，append/3 的递归定义不仅为我们提供了验证列表是否是另外两个列表的串联的可能性，它还生成了满足与完全或部分逻辑关系的所有可能答案实例化列表。