递归是Prolog中最主要而又最难于掌握的概念之一，Prolog是一门声明式编程语言，当你处理事物集合时，如列表或树，你会经常使用递归而不是迭代。此外，由于我们经常需要控制回溯的程度，我们最好需要了解一下截断这个概念（在我的另一篇经验会提到它）。
工具/原料
电脑
SWI-Prolog
牛刀小试——寻找祖先和后代的程序
1、让我们先从这一个简单的例子来了解递归的性质吧。在ancestor子句中的一个子句会使用ancestor子句。在这个例子中，ancestor(Z, Y)是一个递归的子目标。fath髫潋啜缅er 是实现递归子目标的核心事实。规则ancestor/2有两个子句。如果一个规则由多个子句组成，那么其子句为真，则这个规则为真。可以把子句间的逗号看成是条件“与”的关系，把子句之间的句号看成是条件“或”的关系。
2、我们可以测试一下这个规则：我们首先询问命题ancestor(john_boy_sr, john_boy_jr).和ancestor(zeb, john_boy_jr).是否为真，接着给出变量Who，分别寻找zeb的后代和john_boy_jr的祖先。我们已经可以在知识库中使用这个规则实现两个目的：寻找祖先和后代。
渐入佳境——利用递归计算阶乘
1、一稍僚敉视个整数的阶乘定义为，该数与小于它的全部正整数的积，一个整型数的阶乘用该数及后面的感叹号表示（!）。比如：5! = 5 × 4 ×3 × 2 × 1。一般形式为：n! = n × (荏鱿胫协n - 1) × (n - 2) ×……× 3 × 2 × 1然而，一个整型数的阶乘还可能表示为这个整型数与公比其小1 的那个整型数的阶乘的乘积，例如：5!=5×4!。这种阶乘的定义方式就体现了递归，因为它利用阶乘自定义阶乘。因此，任一正整数的阶乘可用下面递归定义给出：n! = n × (n-1)!
2、在数学的定义上，0的阶乘等于1。因此，阶乘的完整定义如下：0! = 1（停止条件）n! = n x (n - 1)!（递归定义）转换成Prolog程序如下图所示：
3、在询问后，得到结果后按回车。运行结果如图所示。值得注意的是，在知识库中停止条件应该放在递归规则前面，这一点是至关重要的。因为如果不是这样，停止条件将永远不会满足。假如把规则放在停止条件前面，那么Prolog重复进入知识库时将首先遇到它，并与其进行匹配，即使是应满足停止条件时，也绝不会与停止条件匹配，从而引起无穷递归。
趁热打铁——斐波那契数列
1、数学的斐波那契数列是一个正整数数列，它与黄金比例有着密切的联系。该数列的下一个数是由其前面两个数相加得到的，头两个数均为1。该数列如下：1，1，2，3，5，8，13，21，34，55，……通式为：f(1) = 1 （两个停止条件）f(2) = 1f(n) = f(n-1) + f(n-2) （递归规则）
2、这里用Num1、Num2这两个变量分别来表示序数Num项的前面两项；变量Term1和Term2分别表示前两项斐波那契数的结果。来转换成Prolog程序如下图所示：
3、运行后的结果如下图所示。从截图可以看出，这些递归的程序还存在一些问题，比如在已经得出结果后，如果按“;”键试图查找另一个解时，会出现错误的答案，甚至开始报错。因为如果查找另一个结果，会重新进入递归条件，会再次减去数字，因而会报错。我将会在下次介绍Prolog的另一个机制——截断。
