Prolog递归

  • Z时代
  • 2024-01-10
  • 分类：综合

例子

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

  • Base (non-recursive) 子句：通常情况下，base-caserule(s)将代表example(s)您尝试解决的最小问题 - 一个没有成员的列表，或者只有一个成员，或者如果您正在使用树结构，它可能处理一棵空树，或一棵只有一个节点的树，等等。它非递归地描述了递归过程的基础。

  • 递归（继续）子句：包含任何必需的逻辑，包括对自身的调用、继续递归。

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

% 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用字母替换类似自由变量的符号，以获得更好的概览：

?- 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
...

在第一个答案，基本情况是模式匹配和前导实例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不仅为我们提供了验证列表是否是其他两个列表的连接的可能性，它还生成满足完全或部分实例化的逻辑关系的所有可能答案列表。

以上是 Prolog递归 的全部内容， 来源链接： utcz.com/z/358548.html

回到顶部