|
递归的详细介绍及在解题中的应用
递归应用
直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。
一个比较经典的描述是老和尚讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在讲故事，他说从前有座山，……。这样没完没了地反复讲故事，直到最后老和尚烦了停下来为止。
反复讲故事可以看成是反复调用自身，但如果不能停下来那就没有意义了，所以最终还要能停下来。递归的关键在于找出递归方程式和递归终止条件。即老和尚反复讲故事这样的递归方程式要有，最后老和尚烦了停下来这样的递归的终止条件也要有。
阶乘的算法可以定义成函数
n*f(n－1) (n>0)
f(n)＝ f(n)=1 (n=0)
当n>0时，用f(n-1)来定义f(n)，用f(n-1-1)来定义f(n-1)……，这是对递归形式的描述。
当n=0时，f(n)=1，这是递归结束的条件。
函数都可以找到相应的非递归方式定义： n!=1*2*3*…*(n-1)*n
边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。
递归算法一般用于解决三类问题：
⑴. 数据的定义形式是按递归定义的。
比如阶乘的定义。
例1 又如裴波那契数列的定义：f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2
对应的递归程序为：
var n:integer;
function f(n:integer):longint;
begin
case n of
0:f:=1; {递归结束条件}
1:f:=2;
else
f:=f(n-1)+f(n-2) ｛递归调用｝
end
end;
begin
readln(n);
writeln(f(n));
end.
这类递归问题往往又可转化成递推算法，递归边界作为递推的边界条件。
例2 Ackerman函数
当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。
Ackerman函数A(m，n)定义如下：
┌ n+1 当m=0时
AKM ( m , n ) = │ AKM( m-1 ,1) 当m≠0 ，n=0时
└ AKM( m-1, AKM( m,n-1)) 当m≠0, n ≠ 0时
Ackerman函数却无法找到非递归的定义。
⑵. 问题解法按递归算法实现。例如回溯等。
⑶. 数据的结构形式是按递归定义的。如树的遍历, 图的搜索等。
递归解决实际问题的例子很多，如经典的梵塔问题。
例2 梵塔问题：有n个半径各不相同的圆盘，按半径从大到小，自下而上依次套在A柱上，另外还有B、C两根空柱。要求将A柱上的n个圆盘全部搬到C柱上去，每次只能搬动一个盘子，且必须始终保持每根柱子上是小盘在上，大盘在下。
在移动盘子的过程当中发现要搬动n个盘子，必须先将n-1个盘子从A柱搬到B柱去，再将A柱上的最后一个盘子搬到C柱，最后从B柱上将n-1个盘子搬到C柱去。搬动n个盘子和搬动n-1个盘子时的方法是一样的，当盘子搬到只剩一个时，递归结束。
程序如下：
var a,b,c,number:integer;
procedure move(n,a,b,c:integer);
begin
if n=1 then writeln(a,'->',c)
else
begin
move(n-1,a,c,b);
writeln(a,'->',c);
move(n-1,b,a,c)
end;
end;
begin
write('the number of dish:');
readln(number);
move(number,1,2,3);
readln
end.
自然数的拆分，数字的拆分等都可以用到递归算法。
例3 要求找出具有下列性质的数的个数(包含输入的自然数n)：
先输入一个自然数n(n<=500),然后对此自然数按照如下方法进行处理:
①. 不作任何处理;
②. 在它的左边加上一个自然数,但该自然数不能超过原数的一半;
③. 加上数后,继续按此规则进行处理,直到不能再加自然数为止.
样例: 输入: 6
满足条件的数为 6
16
26
126
36
136
输出: 6
这道题只需求出满足条件的数的个数，在n值不大的情况下用递归求解比较方便，因为它本身题目的条件就是递归定义的。
递归的样例程序如下：
var n,i:integer;
s:real;
procedure qiu(x:integer);
var k:integer;
begin
if x<>0 then
begin
s:=s+1;
for k:=1 to x div 2 do qiu(k)
end
end;
begin
readln(n);
s:=0;
qiu(n);
writeln(s:2:0)
end.
递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
递归小结
优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。
缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
解决方法：在递归算法中消除递归调用，使其转化为非递归算法。
1.采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。
2.用递推来实现递归函数。
3.通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。
后两种方法在时空复杂度上均有较大改善，但其适用范围有限。
『题1』直线的交点数
平面上有n条直线，且无三线共点，问这些直线能有多少种不同的交点数。
输入：n (n<=20)
输出：若干行，列出所有相交方案，其中每一行为一个可能的交点数。
[ 样例 ]：
输入：4
输出：0
3
4
5
6
（表示4条直线的情况下，可能有0，3，4，5，6个交点）
『题2』集合的划分
设s是一个具有n个元素的集合，s＝{a1,a2, …,an},现将s划分为k个满足下列条件的子集合s1，s2，……，sk，且满足：
（1）si<>ф
（2）si 交 sj=ф
（3）s1并s2并s3并……并sk＝s
则称s1，s2，……，sk是集合s的一个划分。请你确定n个元素a1,a2, …,an放入k个无标号盒子中去的划分数s（n，k）。
输入：n
k （0<k<=n<30）
输出：s（n，k）
[ 样例 ]：
输入：4
3
输出：6
『题3』
Ackerman 函数定义如下：请写出递归算法。
┌ n+1 当m=0时
AKM ( m , n ) = │ AKM( m-1 ,1) 当m≠0 ，n=0时
└ AKM( m-1, AKM( m,n-1)) 当m≠0, n ≠ 0时
① 写出计算Ack(m，n)的递归算法程序。
② 写出计算Ack(m，n)的非递归算法程序。
『题4』
用递归算法把任一给定的十进制正整数m（m<=32000）转换成八进制数输出。
[ 样例 ]：
输入： 765 （即m的值）
输出：765＝（1375）8 |
网友评论：（只显示最新10条。评论内容只代表网友观点，与本站立场无关！） 
