递归算法
时间：2006-11-06 21:55 来源：本站原创 作者：Grant 阅读：次
递归算法
程序调用自身的编程技巧称为递归（ recursion）。
一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
注意：
(1) 递归就是在过程或函数里调用自身;
(2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
一个比较经典的描述是老和尚讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在讲故事，他说从前有座山， ……。这样没完没了地反复讲故事，直到最后老和尚烦了停下来为止。
反复讲故事可以看成是反复调用自身，但如果不能停下来那就没有意义了，所以最终还要能停下来。递归的关键在于找出递归方程式和递归终止条件。即老和尚反复讲故事这样的递归方程式要有，最后老和尚烦了停下来这样的递归的终止条件也要有。
阶乘的算法可以定义成函数
当 n>0时，用 f(n-1)来定义 f(n)，用 f(n-1-1)来定义 f(n-1)……，这是对递归形式的描述。
当 n=0时， f(n)=1，这是递归结束的条件。
例：用递归策略求N!的解。
N!=1*2*3*...*N
分析：
(1) 不运用递归的解法
(2) 运用递归策略
N!=1*2*3*...*N
=[1*2*3*...*(N-1)]*N
(N-1)!=1*2*3*...*(N-1)
设 f(N)=N!
那么 f(N-1)=(N-1)!
则 f(N)=f(N-1)*N
这就是递归式子，由于式子中有N-1，所以N>=1，递归出口的条件是N=1时。
函数模式：
function f(n:integer):longint;
var
...
begin
if 递归出口的时候 then
f:=1
else
f:=f(n-1)*n;
end;
递归算法一般用于解决三类问题：
⑴. 数据的定义形式是按递归定义的。
比如阶乘的定义。
例 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 梵塔问题：有 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.
递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
程序调用自身的编程技巧称为递归（ recursion）。
一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
注意：
(1) 递归就是在过程或函数里调用自身;
(2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
一个比较经典的描述是老和尚讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在讲故事，他说从前有座山， ……。这样没完没了地反复讲故事，直到最后老和尚烦了停下来为止。
反复讲故事可以看成是反复调用自身，但如果不能停下来那就没有意义了，所以最终还要能停下来。递归的关键在于找出递归方程式和递归终止条件。即老和尚反复讲故事这样的递归方程式要有，最后老和尚烦了停下来这样的递归的终止条件也要有。
阶乘的算法可以定义成函数
当 n>0时，用 f(n-1)来定义 f(n)，用 f(n-1-1)来定义 f(n-1)……，这是对递归形式的描述。
当 n=0时， f(n)=1，这是递归结束的条件。
例：用递归策略求N!的解。
N!=1*2*3*...*N
分析：
(1) 不运用递归的解法
(2) 运用递归策略
N!=1*2*3*...*N
=[1*2*3*...*(N-1)]*N
(N-1)!=1*2*3*...*(N-1)
设 f(N)=N!
那么 f(N-1)=(N-1)!
则 f(N)=f(N-1)*N
这就是递归式子，由于式子中有N-1，所以N>=1，递归出口的条件是N=1时。
函数模式：
function f(n:integer):longint;
var
...
begin
if 递归出口的时候 then
f:=1
else
f:=f(n-1)*n;
end;
递归算法一般用于解决三类问题：
⑴. 数据的定义形式是按递归定义的。
比如阶乘的定义。
例 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 梵塔问题：有 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.
递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
(责任编辑：admin)
顶一下
(0)
0%
踩一下
(0)
0%
相关内容
- ·提高access的启动速度【译文技巧】
- ·浅谈断号重续的利弊和方法
- ·分析使用Len函数判断字符串为空的原理
- ·mdb快捷方式拖到桌面，打开会出现“不
- ·Access设计表字段是的注意事项
- ·学习别人示例的技巧方法
- ·SQL中获取两日期之间的值
- ·成为伟大开发者的“九步曲”
- ·面向初学者的窗体功能设计集成
- ·WINRAR打包视频演示全过程
- ·《VB函数参考手册》电子书
- ·ACCESS数据表中数据类型“是/否”转为S
- ·Application与Docmd对象Quit方法区别探
- ·获取ACCESS安装路径的二法(分享)
- ·JAVA+ACCESS编程体会
- ·Access 2003开发者扩展工具集概述
最新内容
推荐内容