C 语言高级编程技术
8.1 递归程序设计
8.1.1  递归与递归程序设计
递归技术在算法和程序设计中是一种十分有用的技术，C 语言提供了支持递归定义的机制和手段。递归有直接递归和间接递归两种。在一个函数的定义中出现了对自身的调用，称之为直接递归；一个函数f 的定义中包含了对函数g 的调用，而g 的实现过程又调用了f ，即函数调用形成了一个环状调用链, 这种方式称之为间接递归。
例8.1 编写一个递归函数，求n 的阶乘值n ！。
若用fact(n)表示n 的阶乘值，根据阶乘的数学定义可知：
⎝⎛>-==0
)1(*01)(n n fact n n n fact  显然, 当n>0时，fact(n)是建立在fact(n-1)的基础上。由于求解fact(n-1)的过程与求解fact(n)的过程完全相同，只是具体实参不同，因而在进行程序设计时，不必再仔细考虑fact(n-1)的具体实现，只需借助递归机制进行自身调用即可。于是求n 的阶乘值fact(n)的具体实现为：
long fact(int n)
{
long m;
if (n == 0)
return(1);
else
{
m=n*fact(n-1);
return(m);
}
}
例8.2  编写一个递归函数，求Fibonacci 数列第n 项的值。
若用Fibona(n)表示Fibonacci 数列第n 项的值，根据Fibonacci 数列的计算公式：
⎩
⎨⎧>+==2n 2)-Fibona(n 1)-Fibona(n 2,11Fibona(n)n  可知当n>2 时，Fibonacci 数列第n 项的值等于第n-1项的值与第n-2项的值相加之和，而Fibonacci 数列第n-1项和第n-2项值的求解又分别取决于它们各自前两项之和。总之，Fibona(n-1)和Fibona(n-2)的求解过程与Fibona(n)的求解过程相同，只是具体实参不同。利用以上这种性质，我们在进行程序设计时便可以使用递归技术，Fibona(n-1)和Fibona(n-2)的求解只需调用函数Fibona 自身加以实现即可。具体实现为：
int Fibona(int n)
{
int  m;
if  (n==1 || n==2)
return (1);
else
{
m=Fibona(n-1)+ Fibona(n-2);
return (m);
}
}
从上面两个实例可以看出，要使用递归技术进行程序设计，首先必须将要求解的问题分解成若干子问题，这些子问题的结构与原问题的结构相同，但规模较原问题小。由于子问题与原问题结构相同，因而它们的求解过程相同，在进行程序设计时，不必再仔细考虑子问题的求解，只需借助递归机制进行函数自身调用加以实现，然后利用所得到的子问题的解组合成原问题的解即可；而递归程序在执行过程中，通过不断修改参数进行自身调用，将子问题分解成更小的子问题进行求解，直到最终分解成的子问题可以直接求解为止。
综上所述，递归程序设计具有以下两个特点：
（1）具备递归出口。递归出口定义了递归的终止条件，当程序的执行使它得到满足时，递归执行过程便终止。有些问题的递归程序可能存在几个递归出口；
（2）在不满足递归出口的情况下，根据所求解问题的性质，将原问题分解成若干子问题，子问题的求解通过以一定的方式修改参数进行函数自身调用加以实现，然后将子问题的解组合成原问题的解。递归调用时，参数的修改最终必须保证递归出口得以满足。
8.1.2  递归程序执行过程的分析
递归程序的执行过程分为递推和回归两个阶段。
在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如例8.2中，求解Fibona(n)，把它推到求解Fibona(n-1)和Fibona(n-2)。即是说，为计算Fibona(n)，必须先计算Fibona(n-1)和Fibona(n-2)，而计算Fibona(n-1)和Fibona(n-2)，又必须先计算Fibona(n-3)和Fibona(n-4)。依次类推，直至计算Fibona(1)和Fibona(2)，分别能立即得到结果1和1。在递推阶段，必须要有终止递归的情况。例如在函数Fibona中，当n为1和2的情况。
在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如得到Fibona(1)和Fibona(2)后，返回得到Fibona(3)的结果，……，在得到了Fibona(n-1)和Fibona(n-2)的结果后，返回得到Fibona(n)的结果。
在编写递归函数时要注意，函数中的局部变量和参数知识局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各有自己的参数和局部变量。
由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数Fibona(n)应采用递推算法，即从斐波那契数列的前两项出发，逐次由前两项计算出下一项，直至计算出要求的第n项。
由于递归调用是对函数自身的调用，在一次函数调用未结束之前又开始了另一次函数调用。这时为函数的运行所分配的空间在结束之前是不能回收的，必须保留。这也意味着函数自身的每次不同调用，就需要分配不同的空间。只有当最后一次调用结束后，才释放最后一次调用所分配的空间，然后返回上一层调用，调用结束后，释放调用所分配的空间，再返回它的上一层调用，这样逐层返回，直至返回到第一次调用，当第一次调用结束后，释放调用所分配的空间，整个递归调用才完成。
在例8.1中，给出了一个求阶乘的函数。下面以求4!为例，其调用过程如图8-1所示。
要求4!，即要求的fact(4)值。
图8-1 递归函数调用的执行过程
8.1.3 递归算法的优缺点
递归函数的主要优点是可以把算法写的比使用非递归函数时更清晰更简洁，而且某些问题，特别是与人工智能有关的问题，更适宜用递归方法。
递归算法的缺点，一是需要额外的内存开销，特别是当递归层次较大时，递归函数需要占用的堆栈空间相当大。二是递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。总之，递归算法要比解决同样问题的非递归算法效率低一些。内存空间需求更多一些。
大多数用递归算法解决的问题，都可以到相应的非递归算法，只有少数问题的求解只有递归算法。由于递归算法具有效率低、内存消耗大等缺点，在设计程序时，若有比较好的非递归算法，应尽量采用非递归算法。
8.1.4  递归程序设计的应用实例
例8.3编程实现将正整数转换为字符串。要求在主函数中输入正整数，转换以及输出编一递归函数完成。
本例的关键在于设计一个递归函数完成正整数n到字符串的转换，实现该函数的一个基本思想为：从高位到低位分别取出n的每一位上的数字，将它们转换成对应的字符后，按其原有的顺序输出；而在此转
换过程中，将n前面的若干位（除个位外）对应的整数转换成字符串的过程与将整个整数转换成字符串的过程完全相同，只是处理的对象不同，因此可以通过递归调
用实现，然后在此基础上再将n 的个位数字转换成字符输出即可。显然，若n 前面的若干位（除个位外）对应的整数为0时，递归调用应该终止。程序为：
#include <stdio.h>
void convert(int n)
{
int i,c;
if ((i=n/10)!=0)
convert(i);
c= n%10+ '0';
putchar(c);
}
void main()
{
int a;
scanf("%d",&a);
convert(a);
}
例8.4 编程求两个正整数的最大公约数。要求编写一个递归函数求最大公约数。
c语言用递归函数求n的阶乘
求最大公约数gcd(m,n)的求解公式为：
⎪⎩
⎪⎨⎧=<=其它          m%n)gcd(n,0n                          m  n m                m)gcd(n,),gcd(n m
由于以上最大公约数的定义本身即为递归定义，因此采用递归方式实现求m 和n 的最大公约数问题十分方便，将n=0作为递归的终止条件，其它情况只需按公式进行递归调用即可。程序为：
#include <stdio.h>
int gcd(int m,int n)
{
int k;
if (n==0)
return(m);
else if (n>m)
return(gcd(n,m));
else
{
k=m%n;
return(gcd(n,k));
}
}
void main()
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d",gcd(a,b));
}
例8.5汉诺塔（Hanoi ）问题。汉诺塔问题是一个著名的问题。约十九世纪末，在欧洲的商
店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔，游戏的目的是将最左边A杆上的圆盘，借助最右边的C杆，全部移到中间的B杆上，条件是一次仅能移动一个盘，且不允许大盘放在小盘的上面。如图8-2所示。
图8-2 汉诺塔
由于问题中给出的圆盘移动条件是：一次仅能移动一个盘，且不允许大盘放在小盘的上面，这样64个盘子的移动次数是：18,446,744,073,709,551,616。这是一个天文数字，若每一微秒可能计算（并不输出）一次移动，那么也需要几乎一百万年。我们仅能出问题的解决方法并解决较小n值时的汉诺塔，但目前由于计算机的速度还不够"快"，尚不可能用计算机解决64层的汉诺塔。
按照上面给出的方法分析问题，出移动圆盘的递归算法。
设要解决的汉诺塔共有n个圆盘，对A杆上的全部n个圆盘从小到大顺序编号，最小的圆盘为1号，次之为2号，依次类推，则最下面最大的圆盘的编号为n。
第1步，先将问题简化。假设A杆上只有一个圆盘，即汉诺塔只有一层n=1，则只要将1号盘从A杆上移到B杆上即可。
第2步，对于一个有n（n>1）个圆盘的汉诺塔，将n个圆盘分为两部分：上面的n-1个圆盘和最下面的n号圆盘。
第3步，将"上面的n-1个圆盘"看成一个整体，为了解决n个圆盘的汉诺塔，可以按如下方式进行操作：
① A杆上面的n-1个盘子，借助B杆，移到C杆上(如图8-3所示)；
图8-3
② A杆上剩下的n号盘子移到B杆上(如图8-4所示)；
图8-4
整理上述分析结果，把第1步中化简问题的条件作为递归结束条件，将第3步分析得到的算法作为递归算法，可以写出如下完整的递归算法描述。
定义一个函数movedisc(n，Aneedle，Bneedle，Cneedle)。该函数的功能是：将Aneedle杆上的n个圆盘，借助Cneedle杆，移动到Bneedle杆上。这样移动n个圆盘的递归算法描述如下：movedisc(n，Aneedle，Bneedle，Cneedle)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。