1、Comment 创创1: 页：237C语言高级编程技术 237C语言高级编程技术8.1 递归程序设计8.1.1 递归与递归程序设计递归技术在算法和程序设计中是一种十分有用的技术，C 语言提供了支持递归定义的机制和手段。递归有直接递归和间接递归两种。在一个函数的定义中出现了对自身的调用，称之为直接递归；一个函数 f的定义中包含了对函数 g的调用，而 g的实现过程又调用了 f，即函数调用形成了一个环状调用链, 这种方式称之为间接递归。例 8.1 编写一个递归函数，求 n的阶乘值 n！。若用 fact(n)表示 n的阶乘值，根据阶乘的数学定义可知： 0)1(*)(factfct显然, 当 n0时，f
2、act(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);elsem=n*fact(n-1);return(m);例 8.2 编写一个递归函数，求 Fibonacci数列第 n项的值。若用 Fibona(n)表示 Fibonacci数列第 n项的值，根据 Fibonacci数列的计
3、算公式：2)-Fiboa(1)-ia(,1Fibo()可知当 n2 时，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
4、 | n=2) return (1);else m=Fibona(n-1)+ Fibona(n-2);return (m);从上面两个实例可以看出，要使用递归技术进行程序设计，首先必须将要求解的问题分解成若干子问题，这些子问题的结构与原问题的结构相同，但规模较原问题小。由于子问题与原问题结构相同，因而它们的求解过程相同，在进行程序设计时，不必再仔细考虑子问题的求解，只需借助递归机制进行函数自身调用加以实现，然后利用所得到的子问题的解组合成原问题的解即可；而递归程序在执行过程中，通过不断修改参数进行自身调用，将子问题分解成更小的子问题进行求解，直到最终分解成的子问题可以直接求解为止。综上所述，递
5、归程序设计具有以下两个特点：（1）具备递归出口。递归出口定义了递归的终止条件，当程序的执行使它得到满足时，递归执行过程便终止。有些问题的递归程序可能存在几个递归出口；（2）在不满足递归出口的情况下，根据所求解问题的性质，将原问题分解成若干子问题，子问题的求解通过以一定的方式修改参数进行函数自身调用加以实现，然后将子问题的解组合成原问题的解。递归调用时，参数的修改最终必须保证递归出口得以满足。8.1.2 递归程序执行过程的分析递归程序的执行过程分为递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为 n）的求解推到比原问题简单一些的问题（规模小于 n）的求解。例如例 8.2 中，求解 Fibo
6、na(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
7、(2)后，返回得到 Fibona(3)的结果，在得到了 Fibona(n-1)和Fibona(n-2)的结果后，返回得到 Fibona(n)的结果。在编写递归函数时要注意，函数中的局部变量和参数知识局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各有自己的参数和局部变量。由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。例如上例计算斐波那契数列的第 n 项的函数 Fibona(n)应采用递推算法，即从斐波那契数列的前两项出发，
8、逐次由前两项计算出下一项，直至计算出要求的第 n 项。由于递归调用是对函数自身的调用，在一次函数调用未结束之前又开始了另一次函数调用。这时为函数的运行所分配的空间在结束之前是不能回收的，必须保留。这也意味着函数自身的每次不同调用，就需要分配不同的空间。只有当最后一次调用结束后，才释放最后一次调用所分配的空间，然后返回上一层调用，调用结束后，释放调用所分配的空间，再返回它的上一层C 语言高级编程技术 239调用，这样逐层返回，直至返回到第一次调用，当第一次调用结束后，释放调用所分配的空间，整个递归调用才完成。在例 8.1 中，给出了一个求阶乘的函数。下面以求 4!为例，其调用过程如图 8-1 所
9、示。要求 4!,即要求的 fact(4)值。图 8-1 递归函数调用的执行过程8.1.3 递归算法的优缺点递归函数的主要优点是可以把算法写的比使用非递归函数时更清晰更简洁，而且某些问题，特别是与人工智能有关的问题，更适宜用递归方法。递归算法的缺点，一是需要额外的内存开销，特别是当递归层次较大时，递归函数需要占用的堆栈空间相当大。二是递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。总之，递归算法要比解决同样问题的非递归算法效率低一些。内存空间需求更多一些。大多数用递归算法解决的问题，都可以找到相应的非递归算法，只有少数问题的求解只有递归算法。由于递归算法具有效
10、率低、内存消耗大等缺点，在设计程序时，若有比较好的非递归算法，应尽量采用非递归算法。8.1.4 递归程序设计的应用实例例 8.3 编程实现将正整数转换为字符串。要求在主函数中输入正整数，转换以及输出编一递归函数完成。本例的关键在于设计一个递归函数完成正整数 n 到字符串的转换，实现该函数的一个基本思想为：从高位到低位分别取出 n 的每一位上的数字，将它们转换成对应的字符后，按其原有的顺序输出；而在此转换过程中，将 n 前面的若干位（除个位外）对应的整数转换成字符串的过程与将整个整数转换成字符串的过程完全相同，只是处理的对象不同，因此可以通过递归调用实现，然后在此基础上再将 n 的个位数字转换成
11、字符输出即可。显然，若 n 前面的若干位（除个位外）对应的整数为 0 时，递归调用应该终止。程序为：#include 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“,convert(a);例 8.4 编程求两个正整数的最大公约数。要求编写一个递归函数求最大公约数。求最大公约数 gcd(m,n)的求解公式为： 其 它 m%n)gcd(,0 ,),c(n由于以上最大公约数的定义本身即为递归定义，因此采用递归方式实现求 m 和 n 的最大公约
12、数问题十分方便，将 n=0 作为递归的终止条件，其它情况只需按公式进行递归调用即可。程序为：#include int gcd(int m,int n)int k;if (n=0) return(m); else if (nm) return(gcd(n,m);elsek=m%n;return(gcd(n,k);void main()int a,b;C 语言高级编程技术 241scanf(“%d%d“,printf(“%d“,gcd(a,b);例 8.5 汉诺塔（Hanoi ）问题。汉诺塔问题是一个著名的问题。约十九世纪末，在欧洲的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而
13、下、由小到大顺序串着由 64 个圆盘构成的塔，游戏的目的是将最左边 A 杆上的圆盘，借助最右边的 C 杆，全部移到中间的 B 杆上，条件是一次仅能移动一个盘，且不允许大盘放在小盘的上面。如图 8-2 所示。图 8-2 汉诺塔由于问题中给出的圆盘移动条件是：一次仅能移动一个盘，且不允许大盘放在小盘的上面，这样 64 个盘子的移动次数是：18,446,744,073,709,551,616。这是一个天文数字，若每一微秒可能计算（并不输出）一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小 n 值时的汉诺塔，但目前由于计算机的速度还不够“快“ ，尚不可能用计算机解决 64层的汉诺
14、塔。按照上面给出的方法分析问题，找出移动圆盘的递归算法。设要解决的汉诺塔共有 n 个圆盘，对 A 杆上的全部 n 个圆盘从小到大顺序编号，最小的圆盘为 1 号，次之为 2 号，依次类推，则最下面最大的圆盘的编号为 n。第 1 步，先将问题简化。假设 A 杆上只有一个圆盘，即汉诺塔只有一层 n=1，则只要将 1号盘从 A 杆上移到 B 杆上即可。第 2 步，对于一个有 n（n1）个圆盘的汉诺塔，将 n 个圆盘分为两部分：上面的 n-1 个圆盘和最下面的 n 号圆盘。第 3 步，将“上面的 n-1 个圆盘 “看成一个整体，为了解决 n 个圆盘的汉诺塔，可以按如下方式进行操作： A 杆上面的 n-1
15、 个盘子，借助 B 杆，移到 C 杆上( 如图 8-3 所示) ；图 8-3 A 杆上剩下的 n 号盘子移到 B 杆上( 如图 8-4 所示) ；Comment cqup2: 图 8-4整理上述分析结果，把第 1步中化简问题的条件作为递归结束条件，将第 3步分析得到的算法作为递归算法，可以写出如下完整的递归算法描述。定义一个函数 movedisc(n，Aneedle，Bneedle，Cneedle)。该函数的功能是：将 Aneedle杆上的 n个圆盘，借助 Cneedle杆，移动到 Bneedle杆上。这样移动 n个圆盘的递归算法描述如下：movedisc(n，Aneedle ，Bneedle
16、，Cneedle) if ( n=1 )将 n号圆盘从 Aneedle上移到 Bneedle;else movedisc(n-1，Aneedle，Cneedle ，Bneedle) 将 n号圆盘从 Aneedle上移到 Bneedle; movedisc(n-1，Cneedle，Bneedle，Aneedle)按照上述算法可以编出如下程序。#include int i=0; /* 移动圆盘数量计数器 */void movedisc(unsigned int n, char Aneedle, char Bneedle, char Cneedle) if(n=1)printf(“%2d-(%2d)
17、: %c = %cn“,+i,n,Aneedle,Bneedle);/* 将 Aneedle上的一个圆盘移到 Bneedle上 */else movedisc(n-1, Aneedle, Cneedle, Bneedle);/* 将 Aneedle上的 n-1个圆盘借助 Bneedle移到 Cneedle上 */printf(“%2d-(%2d): %c = %cn“,+i,n,Aneedle,Bneedle);/* 将 Aneedle上的一个圆盘移到 Bneedle上 */movedisc(n-1,Cneedle,Bneedle,Aneedle);/* 将 Cneedle上的 n-1个圆盘借
18、助 Aneedle移到 Bneedle上 */void main( ) unsigned n;printf(“Please enter the number of discs:“);scanf(“%d“, /* 输入 n值 */movedisc(n,a,b,c); /* 将 A上的 n个圆盘借助 C将移动到 B上 */printf(“t Total: %dn“, i);C 语言高级编程技术 2438.2 文本的屏幕输出和键盘输入8.2.1 文本的屏幕输出显示器的屏幕显示模式有两种：文本方式和图形方式。文本方式就是只能显示字符的方式，在文本模式下屏幕上可以显示的最小单位是字符。在文本模式下，坐标
19、原点在屏幕左上角,其坐标为(1,1)，X轴为水平方向，Y轴为垂直方向。Turbo C 的字符屏幕函数主要包括文本窗口大小的设定、窗口颜色的设置、窗口文本的清除和输入输出等函数。这些函数的有关信息均包含在conio.h 头文件中，因此在用户程序中使用这些函数时，必须用include预处理命令将conio.h 包含进程序。1) 文本窗口的定义Turbo C 默认定义的文本窗口为整个屏幕，共有80 列25 行的文本单元。除了这种默认的80 列25 行的文本显示方式外，还可由用户通过textmode（）函数来显式地设置Turbo C 支持的文本显示方式。Textmode（）函数的函数原型为：void
20、textmode(int newmode)；该函数将清除屏幕，以整个屏幕为当前窗口，并移光标到屏幕左上角。newmode 参数的取值见表8-1，既可以用表中指出的方式代码，又可以用符号常量。LASTMODE 方式指上一次设置的文本显示方式，它常用于在图形方式到文本方式的切换。方式 符号常量 显示列行数和颜色0 BW40 4025黑白显示1 C40 4025彩色显示2 BW80 8025黑白显示3 C80 8025彩色显示7 MONO 8025单色显示-1 LASTMODE 上一次的显示方式表8-1 Turbo C 支持的6种显示方式Turbo C 也允许用户根据自己的需要通过使用窗口设置函数w
21、indow()重新设定显示窗口。window()函数的函数原型为：void window(int left, int top, int right, int bottom)；函数中形参（int left，int top）是窗口左上角的坐标，（int right，int bottom）是窗口的右下角坐标，其中（left，top）和（right，bottom）是相对于整个屏幕而言的。例如，要定义一个窗口左上角在屏幕（20，5）处，大小为30 列15 行的窗口可写成：window(20, 5, 50, 25);若window()函数中的坐标超过了屏幕坐标的界限，则窗口的定义就失去了意义，也就是说定义
22、将不起作用，但程序编译连接时并不出错。窗口定义之后，用有关窗口的输入输出函数就可以只在此窗口内进行操作而不超出窗口的边界。一个屏幕可以定义多个窗口，但现行窗口只能有一个（因为DOS 为单任务操作系统）。当需要用另一窗口时，可将定义该窗口的window()函数再调用一次, 此时该窗口便成为现行窗口了。2) 文本窗口颜色和其它属性的设置文本窗口颜色的设置包括背景颜色的设置和字符颜色（即前景色）的设置，使用的函数及其原型为：设置背景颜色函数：void textbackground(int color)；设置字符颜色函数：void textcolor(int color)；有关颜色的定义见表8-2。表
23、中的符号常数与相应的数值等价，二者可以互换。例如设定蓝色背景可以使用textbackground(1)，也可以使用textbackground(BLUE)，两者没有任何区别。符号 常数 数值含义 背景或背景BLACK 0 黑 前景、背景色BLUE 1 蓝 前景、背景色GREEN 2 绿 前景、背景色CYAN 3 青 前景、背景色RED 4 红 前景、背景色MAGENTA 5 洋红 前景、背景色BROWN 6 棕 前景、背景色LIGHTGRAY 7 淡灰 前景、背景色DARKGRAY 8 深灰 用于前景色LIGHTBLUE 9 淡蓝 用于前景色LIGHTGREEN 10 淡绿 用于前景色LIGH
24、TCYAN 11 淡青 用于前景色LIGHTRED 12 淡红 用于前景色LIGHTMAGENTA 13 淡洋红 用于前景色YELLOW 14 黄 用于前景色WHITE 15 白 用于前景色BLINK 128 闪烁 用于前景色表8-2 颜色表Turbo C 另外还提供了一个函数，可以同时设置文本的字符和背景颜色，这个函数是文本属性设置函数,其函数原型为：void textattr(int attr)；参数attr 的值表示颜色形式编码的信息，每一位代表的含义如下：位 7 6 5 4 3 2 1 0B b b b c c c c闪烁 背景颜色 字符颜色字节低四位cccc 设置字符颜色，46 三位
25、bbb 设置背景颜色，第7位B 设置字符是否闪烁。假如要设置一个蓝底黄字，定义方法如下：textattr(YELLOW+(BLUE#include void main()int i;char ch4*8*2; /* 定义ch 字符串数组作为缓存区*/textmode(C80);textbackground(BLUE);textcolor(RED);clrscr();gotoxy(10,10);cprintf(“L:load“);gotoxy(10,11);cprintf(“S:save“);gotoxy(10,12);cprintf(“D:delete“);gotoxy(10,13);cpri
26、ntf(“E:exitrn“);cprintf(“Press any key to continue“);getch();gettext(10,10,18,13,ch); /* 存矩形区文存到ch 缓存区*/clrscr();textbackground(1);textcolor(3);window(20,9,34,14); /* 开一个窗口*/clrscr();cprintf(“1.rn2.rn3.rn4.rn“);/* 纵向写1，2，3，4 */movetext(20,9,34,14,40,10); /* 将矩形区文本复制到另一区域 */puts(“hit any key“);getch();clrscr();cprintf(“press any key to put text“);getch();clrscr();puttext(23,10,31,13,ch); /* 将ch 缓存区所存文本在屏上显示*/getch();5）状态查询函数有时需要知道当前屏幕的显示方式，当前窗口的坐标、当前光标的位置，文本的显示属性等，Turbo C 提供了一些函数得到屏幕文本显示有关信息的函数：void gettextinfo(struct text_info *f)；
