递归作为一种算法设计策略,是程序设计和描述算法的一种有力工具,在程序设计中被广泛应用。尤其在数值计算、数据结构、人工智能、算法设计与分析等领域应用广泛。分析递归算法设计的一般思想与方法、步骤及需解决的关键问题。通過几个经典的可以采用递归实现的算法,详细阐述了如何通过分析问题,找到递归实现的两个基本核心问题,即递归表达式和递归终止条件,并据此编写递归调用函数。 
关键词递归算法;递归函数;算法设计;程序设计
DOIDOI1.1197/rjdk.171715
中图分类号TP312文献标识码A文章编号167278(217)1354
1递归算法理论基础
众所周知,通常把程序调用自身的编程技巧称为递归1,递归作为一种算法设计策略,在程序设计中得到了广泛应用。递归按照调用的方式,可分为直接递归和间接递归两种类型2。
直接递归是指函数在执行过程中直接调用自身;间接递归是指函数在执行过程中调用了其它函数,再经过这些函数调用自身。
递归从字面上看,包含两部分内容,它由两个字组成,即“递”和“归”,“递”表示传送、传达的意思,“归”是返回的意思,从字面上讲递归就是周而复始的循环,但又不是简单的循环。
从数学角度分析,递归的数学模型就是递推原理,在整个过程中,反复实现的都是同一个原理或操作,其本质和数学归纳法3相同。
递归适用于下述问题解决一个问题可以转化为解决其子问题,而其子问题又变成子问题的子问题,而且这些问题的解决都是采用同一个模型,也即需解决的问题和其子问题具有相同的逻辑归纳处理项。有一个子问题是例外的,也即递归结束的那一项,处理方法不适用于上述归纳处理项,当然也不能用这种方法去处理,否则就形成了无穷递归。这就引出了一个归纳终结点以及直接求解的表达式。
根据上述分析,递推可表示如下①步进表达式问题转换为子问题求解的表达式;②结束条件不再适用于步进表达式的情况,亦即何时不再使用步进表达式;③直接求解表达式在结束条件下能够直接计算返回值的表达式;④逻辑归纳项适用于一切非结束条件下子问题的处理,包含上述步进表达式。
由上述对递推原理的分析与描述,相应地可以得到递归求解必须满足的4个特征①必须有可最终达到的终止条件,否则程序将陷入无穷循环;②子问题的规模比原问题小,或更接近终止条件;③子问题可以通过再次递归求解或因满足终止条件而直接求解;④子问题的解应能组合为整个问题的解。
2递归算法设计一般方法
根据上述分析,递归的基本思想是将规模大的问题转化为规模较小的相似子问题加以解决,且这些规模较小子问题的求解过程相对容易,同时规模较小子问题的解足以构成原问题的解。
在算法(函数)实现时,由于解决大问题的方法和解决小问题的方法往往是同一个方法,因此产生了函数调用其自身的情况。解决问题的函数必须有明确的结束条件,也即递归函数必须是收敛的5,这样才可以避免出现无穷递归的情况。
综上,求解递归问题可转化为求解如下3方面问题①如何将原问题划分为规模更小的子问题;②递归终止条件及最小子问题求解方法(递归函数的出口,允许递归函数有多个出口,至少有1个);③找到保证递归规模向出口靠拢的表达式。
将递归求解满足的4个特征归结为解决上述3个问题。实质上,上述3个问题还可作进一步简化,递归问题求解的两个关键点就是找到递归关系式和找出递归终止条件。
3递归算法示例
函数的递归调用是程序设计教学中的一个难点问题,在此,本文通过由浅入深的实例,引导学生逐步掌握使用递归思想进行程序设计的技巧与能力。
例1计算两个正整数m和n的最大公约数
最大公约数,也称为最大公因数或最大公因子,指两个或多个正整数中约数最大的那一个。其主求解方法有质因数分解法、短除法、辗转相除法(欧几里得算法)4、更相减损法等。
质因数分解法,就是对两个正整数分别分解质因数,再把两个数中所有公有的质因数出来连乘,所得到的积就是这两个数的最大公约数。按照上述算法原理,正整数的质因数分解、求两个整数的公有质因数都很难分解为规模更小、求法类似的子问题,因此无法用递归解决。经过类似分析,短除法、更相减损法也都不能递归地实现。
Knuth在《计算机程序设计艺术》第一卷中给出了求两个正整数m和n最大公约数的欧几里德算法,其描述如下
Step1求余数用n除m,令r为余数(这里≤r
}
与辗转相除法类似,可以利用辗转相减法求两个正整数的最大公约数,仍然采用递归方法实现,本文给出具体递归函数。
intgcd(intm,intn){//辗转相减法
if(m==n)//递归终止的条件
returnm;
returngcd(m-n<?n-mm-n,m   该定理可以采用递归树法直观地加以证明,在此不再赘述。 针对折半查找的递归式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介绍的欧几里得算法,可以很方便地使用循環解决。 intgcd(intm,intn){//欧几里德算法 intr=m%n; while(r){m=n;n=r;r=m%n;} returnn; } 例2的Fibonacci数,给出自上而下的递归,用递归树分析其复杂度时,有许多公共字数,造成重复计算,导致其复杂度随n的增加呈指数级增长,若采用自下而上的递归,有F,F1,F2,…,Fn,则可以得到线性时间复杂度的算法,可以用如下循环实现。 intfib(intn){// intf=,f1=1,f,k=2;; while(k++<=n){f=f+f1;f=f1;f1=f;} returnf; } 5.2.2利用栈实现 有些递归需回溯,这就需使用一些变量存储中间计算结果。实际上常常使用栈解决这些问题,如进制转换问题(将一个十进制正整数转换为其它进制数),可以利用辗转相除取余数(逆序)的方法实现,其递归函数描述如下(将十进制整数n转化为b进制字符串s) voidnumconv(char*s,intn,intb){ intlen; if(n==){strcpy(s,“”);return;}//递归终止的条件 numconv(s,n/b,b);//递归表达式 len=strlen(s); slen=“123456789ABC…XYZ”n%b;//当前求得的余数 slen+1=; } 非递归实现时,需将每次求得的余数所对应的字符先存储起来,到程序结束时再逆向依次取出即可组成所得到的字符串,采用《数据结构(C语言版)》7中栈(字符栈)的结构描述及相关操作方法,即可得到非递归算法描述如下 voidnumconvert(char*s,intn,intb){ SqStackS; InitStack(S); while(n){ charc=“123456789ABC…XYZ”n%b; Push(S,c); } while(!StackEmpty(S)){//回溯 charc;inti=; Pop(S,c); si++=c; } si=; } 6结语 本文介绍了递归算法的理论基础、一般方法,阐述了递归算法的复杂度分析方法以及递归算法非递归实现的两种方法。递归可以简化程序设计,高代码可读性,但往往会增加时间开销,使得系统具有较高的时间复杂度。相应的非递归函数虽然效率高,但编写起来比较困难,而且相对而言程序代码的可读性、可维护性较差。随着计算机硬件性能的不断高,程序在很多场合优先考虑的是可读性而不是高效性,因此应鼓励在必情况下使用递归思想实现相关程序设计。 参考文献参考文献 1谭浩强.C程序设计M.第4版.北京清华大学出版社,21. 2吴晓晨.递归程序设计教学方法的研究J.天津科技,217,44(1)6973. 3冯立坤,刘影.数学归纳法的若干应用J.佳木斯大学学报自然科学版,216,34(4)636637. 4高德纳.计算机程序设计艺术(卷1)基本算法M.第3版.李伯民,范明,蒋爱军,译.北京人民邮电出版社,216. 5王海深,马洪英.递归程序设计的理论基础探讨J.小型微型计算机系统,1997,19(2)778. 6THOMASHCORMEN,CHARLESELEISERSON,RONALDLRIVEST,etal.IntroductiontoalgorithmsM.MassachusettsTheMITPress,29. 7严蔚敏,吴伟民.数据结构(C语言版)M.北京清华大学出版社,212.