递归算法设计思想与策略分析
2017-11-02周法国韩智高天
周法国++韩智++高天
摘要：递归作为一种算法设计策略，是程序设计和描述算法的一种有力工具，在程序设计中被广泛应用。尤其在数值计算、数据结构、人工智能、算法设计与分析等领域应用广泛。分析递归算法设计的一般思想与方法、步骤及需要解决的关键问题。通過几个经典的可以采用递归实现的算法，详细阐述了如何通过分析问题，找到递归实现的两个基本核心问题，即递归表达式和递归终止条件，并据此编写递归调用函数。
关键词：递归算法；递归函数；算法设计；程序设计
DOIDOI：10.11907/rjdk.171715
中图分类号：TP312文献标识码：A文章编号：16727800（2017）010003504
1递归算法理论基础
众所周知，通常把程序调用自身的编程技巧称为递归[1]，递归作为一种算法设计策略，在程序设计中得到了广泛应用。递归按照调用的方式，可分为直接递归和间接递归两种类型[2]。
直接递归是指函数在执行过程中直接调用自身；间接递归是指函数在执行过程中调用了其它函数，再经过这些函数调用自身。
递归从字面上看，包含两部分内容，它由两个字组成，即“递”和“归”，“递”表示传送、传达的意思，“归”是返回的意思，从字面上讲递归就是周而复始的循环，但又不是简单的循环。
从数学角度分析，递归的数学模型就是递推原理，在整个过程中，反复实现的都是同一个原理或操作，其本质和数学归纳法[3]相同。
递归适用于下述问题：解决一个问题可以转化为解决其子问题，而其子问题又变成子问题的子问题，而且这些问题的解决都是采用同一个模型，也即需要解决的问题和其子问题具有相同的逻辑归纳处理项。有一个子问题是例外的，也即递归结束的那一项，处理方法不适用于上述归纳处理项，当然也不能用这种方法去处理，否则就形成了无穷递归。这就引出了一个归纳终结点以及直接求解的表达式。
根据上述分析，递推可表示如下：①步进表达式：问题转换为子问题求解的表达式；②结束条件：不再适用于步进表达式的情况，亦即何时不再使用步进表达式；③直接求解表达式：在结束条件下能够直接计算返回值的表达式；④逻辑归纳项：适用于一切非结束条件下子问题的处理，包含上述步进表达式。
由上述对递推原理的分析与描述，相应地可以得到递归求解必须满足的4个特征：①必须有可最终达到的终止条件，否则程序将陷入无穷循环；②子问题的规模要比原问题小，或更接近终止条件；③子问题可以通过再次递归求解或因满足终止条件而直接求解；④子问题的解应能组合为整个问题的解。
2递归算法设计一般方法
根据上述分析，递归的基本思想是将规模大的问题转化为规模较小的相似子问题加以解决，且这些规模较小子问题的求解过程相对容易，同时规模较小子问题的解足以构成原问题的解。
在算法（函数）实现时，由于解决大问题的方法和解决小问题的方法往往是同一个方法，因此产生了函数调用其自身的情况。解决问题的函数必须有明确的结束条件，也即递归函数必须是收敛的[5]，这样才可以避免出现无穷递归的情况。
综上，求解递归问题可转化为求解如下3方面问题：①如何将原问题划分为规模更小的子问题；②递归终止条件及最小子问题求解方法（递归函数的出口，允许递归函数有多个出口，至少要有1个）；③找到保证递归规模向出口靠拢的表达式。
将递归求解满足的4个特征归结为解决上述3个问题。实质上，上述3个问题还可作进一步简化，递归问题求解的两个关键点就是找到递归关系式和找出递归终止条件。
3递归算法示例
函数的递归调用是程序设计教学中的一个难点问题，在此，本文通过由浅入深的实例，引导学生逐步掌握使用递归思想进行程序设计的技巧与能力。
例1计算两个正整数m和n的最大公约数
最大公约数，也称为最大公因数或最大公因子，指两个或多个正整数中约数最大的那一个。其主要求解方法有：质因数分解法、短除法、辗转相除法（欧几里得算法）[4]、更相减损法等。
质因数分解法，就是对两个正整数分别分解质因数，再把两个数中所有公有的质因数提出来连乘，所得到的积就是这两个数的最大公约数。按照上述算法原理，正整数的质因数分解、求两个整数的公有质因数都很难分解为规模更小、求法类似的子问题，因此无法用递归解决。经过类似分析，短除法、更相减损法也都不能递归地实现。
Knuth在《计算机程序设计艺术》第一卷中给出了求两个正整数m和n最大公约数的欧几里德算法，其描述如下：
Step1：求余数：用n除m，令r为余数（这里0≤r Step2：如果r=0，算法终止，n就是答案； Step3：置m←n，n←r，然后返回Step1。 欧几里得算法计算原理依据如下结论：两个正整数的最大公约数（Greatest Common Divisor，gcd）等于较小的那个数和两数相除余数的最大公约数。亦即： gcd（m，n）=gcd（n，m % n）（这里不妨假设m>n） 这样就把求解两个正整数m和n的最大公约数转换为求解更小的两个数n和m%n的最大公约数（1），当m和n有一个数为0，另一个数就是所求的最大公约数（2），（1）和（2）正好对应了递归求解的两个核心问题：递归表达式和递归终止条件。 得到递归实现欧几里得算法求两个正整数最大公约数的函数如下： int gcd（int m， int n）{//欧几里得算法（辗转相除法） if（m*n==0）//递归终止的条件 return m==0？n：m； return gcd（n， m%n）；//递归表达式
}
与辗转相除法类似，可以利用辗转相减法求两个正整数的最大公约数，仍然采用递归方法实现，本文给出具体递归函数。
int gcd（int m， int n）{//辗转相减法
if（m==n）//递归终止的条件
return m；
return gcd（ m-n<0？n-m：m-n， m } 例2计算Fibonacci数 Fibonacci数列又称为黄金分割数列，指如下数列：1，1，2，3，5，8，13，21，…。在数学上，Fibonacci数列被以如下形式递归定义：F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2）。 上述定义给出了递归求解Fibonacci数列的终止条件和递归表达式，可以很简单地得到如下递归函数： long long fib（int n）{ if（n==0 ‖ n==1）//递归终止的条件 return n； return fib（n-1）+fib（n-2）；//递归表达式 } 例3有序序列的折半查找 折半查找，也称二分查找，是针对顺序存储且已经有序排序的数据进行快速查找的一种算法，其基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2]，则找到x，算法中止；如果x 由上分析即可得到递归终止的条件是：待查找元素是查找区间的中点元素（查找成功）或者查找区间不存在（查找失败），即可得到折半查找的递归函数如下： int binarysearch（int a[]， int low， int high， int x）{ while（p<=q）{ int mid = （low+high）/2； if（a[mid]==x） return mid； //查找成功，递归终止的条件 if（x return binarysearch（a， low， mid-1，x）； //递归表达式 else return binarysearch（a， mid+1， high， x）； //递归表达式 } return -1；//查找失败，递归终止的条件 } 例4归并排序 归并排序是建立在归并操作上的一种有效稳定的排序算法，该算法是分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。针对一个无序序列，根据该算法，可以先将该序列分成大小基本相当的两个子序列，并使之有序，再使用归并方法将两个有序的子序列合并成一个有序序列，针对子序列的排序方法仍然可以递归地使用此算法，直到子序列的长度为1时，自动有序，即可得到归并排序的递归函数如下： void mergesort（int a[]， int low， int high）{ if（low int mid=（low+high）/2； mergesort（a，low，mid）；//递归表达式 mergesort（a，mid+1，high）；//递归表达式 merge（a，low，mid，high）；//有序序列的归并操作[7] } } 4递归算法复杂度分析 算法的时间复杂度指计算机执行该算法所需时间，反映程序执行时间随输入规模（记为n）增长而增长的量級，可在很大程度上反映出算法的优劣。实际上，往往在问题规模区域无穷大时（n→∞）分析最坏情况下的时间复杂度。称为算法的渐进时间复杂度，复杂度函数一般表示成问题规模n的函数，用T（n）表示。 例1中求两个正整数最大公约数的时间复杂度为T（m，n）=T（n， m%n）+O（1），例2中求Fibonacci数的时间复杂度为T（n）=T（n-1）+T（n-2）+Θ（1），例3中折半查找的时间复杂度为T（n）=T（n/2）+Θ（1），例4中归并排序的时间复杂度为T（n）=2T（n/2）+Θ（n）。 对于递归算法的时间复杂度分析主要有3种方法：代换法[6]、递归树法和主定理方法。本文主要介绍递归树法和主定理方法。 4.1递归树 递归树法主要是将递归式转换成树的形式，然后利用树的数学概念和特性得知树高和叶子节点个数，从而求解出算法复杂度。这种方法更合适去验证自己的结论，因为它是一种严格的证明过程。下面以一个具体递归式介绍递归树法求解算法时间复杂度的过程，以T（n）=T（n/4）+T（n/2）+Θ（n）为例： 4.2主定理 主定理方法是一种针对递归策略的算法分析方法，可以瞬间估算出算法复杂度，主定理描述如下： 对形如：T（n）=aT（n/b）+f（n）的递归式，其中a≥1，b>1，f（n）渐进趋正，比较f（n）和nlogab，若：①如果存在某常数ε>0，有f（n）=Θ（nlogab-ε），则T（n）=Θ（nlogab）；②如果f（n）=Θ（nlogablgkn），则T（n）=Θ（nlogablgk+1n）；③如果存在某常数ε>0，有f（n）=Ω（nlogab+ε），且对常数c>0与所有足够大的n，有af（n/b）≤cf（n），则T（n）=Θ（f（n））。
该定理可以采用递归树法直观地加以证明，在此不再赘述。
针对折半查找的递归式T（n）=T（n/2）+Θ（1）和归并排序的递归式T（n）=2T（n/2）+Θ（n）均满足定理的第2种情况，故其复杂度分别为Θ（lgn）和Θ（nlgn）；对形如T（n）=4T（n/2）+n的递归式，满足定理第1种情况，故其复杂度为Θ（n2）；对形如T（n）=4T（n/2）+n3的递归式，满足定理第3种情况，故其复杂度为Θ（n3）；对形如T（n）=4T（n/2）+n2/lgn递归式，则不适用于主定理求解。
上述例题中辗转相除法的时间复杂度和折半查找相近，T（n）=T（n-1）+T（n-2）+Θ（1）递归式的时间复杂度是指数阶的。
5递归算法非递归实现
递归就是函数直接调用自己或通过一系列调用语句间接调用自己的过程，是一种描述问题和解决问题的基本方法。递归算法实际上是一种基于分治的方法，它把复杂问题分解为简单问题来求解。对于很多复杂问题（例如hanio塔问题），递归算法是一种自然且合乎逻辑的问题解决方式，但是递归算法的执行效率通常较差，往往需要将递归算法转换为非递归算法。
5.1递归程序工作原理
一个递归函数的调用过程类似于多个函数的嵌套调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。具体而言，递归调用的内部执行过程如下：①开始执行时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；②每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址入栈；③每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。
5.2递归算法非递归实现方法
基于上述递归程序工作原理，一种递归求解算法不需要回溯，可以通过迭代或循环直接求解；一种需要回溯，不能直接求解，需要利用栈保存中间计算结果。由此得到两种递归算法的非递归实现方法：利用循环实现和利用栈实现。
5.2.1利用循环实现
很多递归程序都可以使用循环实现，如例1介绍的欧几里得算法，可以很方便地使用循環解决。
int gcd（int m， int n）{//欧几里德算法
int r=m%n；
while（r）{m=n；n=r；r=m%n；}
return n；
}
例2的Fibonacci数，给出自上而下的递归，用递归树分析其复杂度时，有许多公共字数，造成重复计算，导致其复杂度随n的增加呈指数级增长，若采用自下而上的递归，有F0，F1，F2，…，Fn，则可以得到线性时间复杂度的算法，可以用如下循环实现。
int fib（int n）{//
int f0=0，f1=1，f，k=2；；
while（k++<=n）{f =f0+f1；f0=f1；f1=f；}
return f；
}
5.2.2利用栈实现
有些递归需要回溯，这就需要使用一些变量存储中间计算结果。实际上常常使用栈解决这些问题，如进制转换问题（将一个十进制正整数转换为其它进制数），可以利用辗转相除取余数（逆序）的方法实现，其递归函数描述如下（将十进制整数n转化为b进制字符串s）：
void numconv（char*s， int n， int b）{
int len；
if（n==0）{strcpy（s，“”）；return；}//递归终止的条件
numconv（s，n/b，b）；//递归表达式
len=strlen（s）；
s[len]=“0123456789ABC…XYZ”[n%b]；//当前求得的余数
s[len+1]=0；
}
非递归实现时，需要将每次求得的余数所对应的字符先存储起来，到程序结束时再逆向依次取出即可组成所得到的字符串，采用《数据结构（C语言版）》[7]中栈（字符栈）的结构描述及相关操作方法，即可得到非递归算法描述如下：
void numconvert（char*s， int n， int b） {
SqStack S；
InitStack（S）；
while（n）{
char c=“0123456789ABC…XYZ”[n%b]；
Push（S， c）；
}
while（！StackEmpty（S））{//回溯
char c； int i=0；
Pop（S，c）；
s[i++]=c；
}
s[i]=0；
}
6结语
本文介绍了递归算法的理论基础、一般方法，阐述了递归算法的复杂度分析方法以及递归算法非递归实现的两种方法。递归可以简化程序设计，提高代码可读性，但往往会增加时间开销，使得系统具有较高的时间复杂度。相应的非递归函数虽然效率高，但编写起来比较困难，而且相对而言程序代码的可读性、可维护性较差。随着计算机硬件性能的不断提高，程序在很多场合优先考虑的是可读性而不是高效性，因此应鼓励在必要情况下使用递归思想实现相关程序设计。
参考文献参考文献：
[1]谭浩强.C程序设计[M].第4版.北京：清华大学出版社，2010.
[2]吴晓晨.递归程序设计教学方法的研究[J].天津科技，2017，44（1）：6973.
[3]冯立坤，刘影.数学归纳法的若干应用[J].佳木斯大学学报：自然科学版，2016，34（4）：636637.
[4]高德纳.计算机程序设计艺术（卷1）：基本算法[M].第3版.李伯民，范明，蒋爱军，译.北京：人民邮电出版社，2016.
[5]王海深，马洪英.递归程序设计的理论基础探讨[J].小型微型计算机系统，1997，19（2）：7780.
[6]THOMAS HCORMEN，CHARLES ELEISERSON，RONALD LRIVEST，et al.Introduction to algorithms[M]. Massachusetts：The MIT Press，2009.
[7]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2012.
责任编辑（责任编辑：孙娟）endprint
