递归是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的另一个机制——截断。