Algorithm 版 (精华区)

发信人: zjliu (秋天的萝卜), 信区: Algorithm
标  题: 递归算法
发信站: 哈工大紫丁香 (Wed Aug 13 16:05:06 2003)

*3*…*(N-1)*N 但也可以用下面公式来定义:
    { 1 若N=0
 N!={
    { N*(N-1) 若N>0
    在N>0的公式中,又包括了(N-1)!,这就是N!的递归定义.
    一般说,如果一个对象部分的有自己组成,或者是按他自己定义的,则称之为是递归的

.
递归在数学和计算机学科中经常遇到.利用递归方法可以用有限的语句来定义无限集合,

但在递归定义中至少要有一条是非递归的,即初始定义.否则就会产生逻辑性错误.
    在计算机科学中,递归概念还经常用于递归调用方面,即函数或过程自己调用自己.用

递归调用的算法就是递归算法. 递归调用会产生无终止运算的可能性,因此必须在适当的

情况下终止递归调用(也叫做边界条件).根据递归定义设计的递归算法中,非递归的初始

定义就用做程序的终止条件.
下面举两个递归的典型例子:
( 1) 非波那契(Fibonacci)数列.
数列的递归公式如下:
     { 1 n=1,2
F(n)={
     {F(n-2)+F(n-1) n>2
按照上面的递归公式,可写出如下PASCAL程序
Program fibonacci;
Var n:integer;
Funtion fb(n:integer):integer;
Begin
If n<3 then fb:=1
Else fb:=fb(n-1)+fb(n-2);
End;
Begin
Write(‘n=’);readln(n);
Writeln(‘f(’,n,’)=’,fb(n));
Readln
End.
(2)汉诺(HANOI)塔问题.
    在A,B,C根针上依次移动摆放在针上的大小不一的方片,每个小方片必须位于大方片

的上面.需要把A针上的按从小到大的顺序排列的64个方片,通过B移到C上.
    我们用hanoi(n,A,B,C)来表示把N个方片从A通过B移到C的一个过程.这个过程可以可

以分解为三个步骤:1.把N-1个片从A通过C移到B[hanoi(n-1,A,C,B)]. 2.把A上的最大片

移到C. 3.把B上的N-1片通过A移到C上[hanoi(n-1,B,A,C)].移动N-1个片的方法类似于N

个片的方法.依次类推,直至N=0时为止.
源程序如下:
Program hanoi;
    var n,a,b,c:byte;
procedure hanoi(n,a,b,c:byte);
 begin
   if n=0 then exit;
   hanoi(n-1,a,c,b);
   writeln('move',chr(a),'to',chr(c));
   hanoi(n-1,b,a,c);
end;
begin
   a:=65;b:=66;c:=67;
   write('n=');readln(n);
   hanoi(n,a,b,c);
   readln;
end.

--
╔═══════════════════╗
║★★★★★友谊第一  比赛第二★★★★★║
╚═══════════════════╝

※ 来源:．哈工大紫丁香 bbs.hit.edu.cn [FROM: 202.118.229.162]