Prolog递归
例子
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不仅为我们提供了验证列表是否是其他两个列表的连接的可能性，它还生成满足完全或部分实例化的逻辑关系的所有可能答案列表。