C语言第七章 递归.ppt

1、2020/8/30,主讲教师：四川大学计算机学院 陈良银,1,主讲教师：* 个人主页：*,C语言程序设计（C99版）,四川大学计算机学院,四川大学计算机学院,2020/8/30,主讲教师：四川大学计算机学院 陈良银,2,教材：C语言程序设计（C99版）,陈良银 游洪跃 李旭伟 主编 李志蜀 唐宁九 李 涛 主审 清华大学出版社 2006年9月出版,2020/8/30,主讲教师：四川大学计算机学院 陈良银,3,本书内容,第1章 基础知识 第2章 C语言的基本要素 第3章 变量名、数据类型、运算符和表达式 第4章 C程序基本控制结构 第5章 函数 第6章 数组和指针 第7章 递归 第8章 结构、联

2、合、位运算和枚举类型 第9章 预处理命令 第10章 文件 第11章 高级话题 第12章 C89 Vs C99 实验 （待安排）,2020/8/30,主讲教师：四川大学计算机学院 陈良银,4,分而治之方法,本章主要内容,ARM Vector Table,FIQ,IRQ,(Reserved),Data Abort,Prefetch Abort,Software Interrupt,Undefined Instruction,Reset,1,3,2,回溯法,递归问题求解,2020/8/30,主讲教师：四川大学计算机学院 陈良银,5,本章的节本要求,本章主要介绍C语言的递归方法，通过本章的学习使读者了

3、解各种常见的递归方法，通编写基本的递归程序。 本章将主要介绍两种递归方法：回溯法和分而治之方法。 在网页：,2020/8/30,主讲教师：四川大学计算机学院 陈良银,6,7.1 递归问题求解,递归是函数直接或间接对自已进行调用，在C语言中，所有函数都可以使用递归，数学上的迭代函数都可以用递归进行编程。 例7.1 用递归求阶乘n!S7_1.C。 阶乘可用迭代表示如下：,2020/8/30,主讲教师：四川大学计算机学院 陈良银,7,/* 用递归求阶乘n! */ int Factorial(int n) if (n = 0) /* 递归结束条件成立，结束递归 */ return 1; else /*

4、 递归结束条件不成立，继续进行递归调用 */ return n * Factorial( n - 1); ,2020/8/30,主讲教师：四川大学计算机学院 陈良银,8,下面对递归函数factorial()进行分析，可以先考虑基本情况，然后再由基本情况推算其他情况,2020/8/30,主讲教师：四川大学计算机学院 陈良银,9,简单递归通常都有对函数的入口进行测试的基本情况。,2020/8/30,主讲教师：四川大学计算机学院 陈良银,10,一般递归具有如下的两种形式： 形式1 if () /*递归结束条件成立，结束递归调用 */ 递归结束处理方面的语句; else /*递归结束条件不成立，继续进

5、行递归调用 */ 递归调用方面的语句; ,2020/8/30,主讲教师：四川大学计算机学院 陈良银,11,形式2 if () /* 递归调用条件成立，继续进行递归调用 */ 递归调用方面的语句; else /* 递归调用条件不成立，结束递归调用 */ 递归结束处理方面的语句; ,2020/8/30,主讲教师：四川大学计算机学院 陈良银,12,例7.2 用递归实现将输入的一行字符串按逆序重新输出。S7_2.C /* 将输入的一行字符串按逆序重新输出的递归函数 */ void ReverseDisplay(void) int c; if (c = getchar() != n) /* 递归调用条件

6、成立时，继续递归调用 */ ReverseDisplay(); putchar(c); ,2020/8/30,主讲教师：四川大学计算机学院 陈良银,13,下面对程序代码进行分析： printf(输入一行字符串:n); ReverseDisplay (); 向用户提示后，进行递归调用函数ReverseDisplay ()，当户用按回车键后终止输入。 if (c=getchar() != n) ReverseDisplay (); 用户每输入一个字符，只要没按回车键，都会启动一次对ReverseDisplay()的调用，这时的内部变量c都有自已的存储空间，用于存储所输入的字符，每次调用所输入的字符

7、被堆叠起来，直到按回车键为止。,2020/8/30,主讲教师：四川大学计算机学院 陈良银,14,putchar(c); 当用户输入一行后，才开始显示字符，每次调用ReverseDisplay()都显示存储在内部变量c中的值，显示顺序是先显示回车符n，再显示换行前的最后一个字符，这样下去，直到显示第一个字符为止，这样便实现了输入字符串的逆序显示。,2020/8/30,主讲教师：四川大学计算机学院 陈良银,15,例7.3 修改例7.2，用递归实现将输入的一行文本按词逆序重新输出。 S7_3.C 将例7.2中的getchar()改成接收单词的函数get_word()，并用函数返回单词的下一个字符（如

8、空格符或回车符）,2020/8/30,主讲教师：四川大学计算机学院 陈良银,16,void ReverseDisplay(void) char wMAXWORD; if (GetWord(w) != n) ReverseDisplay(); printf(%s , w); ,2020/8/30,主讲教师：四川大学计算机学院 陈良银,17,/* 输入一个单词,用s返回所输入的单词,函数返回值为所输入单词的下一个字符 */ int GetWord(char *s) int c; while (c = getchar() != ,2020/8/30,主讲教师：四川大学计算机学院 陈良银,18,运行程

9、序时，如果用户输入“this is a string .”，运行界面如下所示：,2020/8/30,主讲教师：四川大学计算机学院 陈良银,19,8.2回溯法,假设问题的解为 n 元组 (x1, x2, , xn)，其中 xi取值于集合Seti，n元组的子组 (x1, x2, , xi) (i n) 为部分解，应满足一定的约束条件。对于已求得的部分解 (x1, x2, , xi) ，在添加xi + 1 Seti +1之后仍然满足约束条件，则可得到一个新的部分解(x1, x2, , xi+1) ,继续添加xi+2 Seti+2，并检查是否满足约束条件，直到添加到xn Setn为止。 如果对于所有取

10、值于集合Seti+1的xi+1都不能得到新的满足约束条件的部分解(x1, x2, ，xi+1)，则从当前子组中删去xi, 回溯到前一个部分解(x1, x2, , xi-1)，重新添加Seti中尚未考察过的xi，看其是否满足约束条件。如此反复进行，直至求得满足约束条件的问题的解，或者证明问题无解。,2020/8/30,主讲教师：四川大学计算机学院 陈良银,20,用类C语言表达回溯法的典型形式如下： void BackTracking(int i, int n) /*假设已求得满足约束条件的部分解(x1,., xi-1)，从xi起继续搜索，直到求 得整个解(x1, x2, , xn)。 */ if

11、 (i n) / 已求得解 输出当前解; ,2020/8/30,主讲教师：四川大学计算机学院 陈良银,21,else / 回溯求解 for (all xi Seti) 修改解的第i个元素为xi; if (x1, x2, , xi)满足约束条件) / 继续求下一个部分解 BackTracking(i + 1, n); 恢复解未修改前的状况;/回溯求新的解 ,2020/8/30,主讲教师：四川大学计算机学院 陈良银,22,例7.4皇后问题求解：在nn棋盘上放置n个皇后，这些皇后中任意两个皇后不能在同一行，同一列，同一条对角线（包括主，次对角线）。如有解则输出所有合法的解。 S7_4.C,2020/

12、8/30,主讲教师：四川大学计算机学院 陈良银,23,/*前i-1个皇后已放置后，为第i个皇后选择合适的位置，a用于表示某列 是否放置有皇后，b表示某条副对角线是否放置有皇后，c表示某条主 对角线是否放置有皇后,x表示皇后所放置的列 */ void TrySolution(int i, int n, int a, int b, int c, int x) int j; if ( i n) /* /in表示第1n个皇后已放置好 */ OutSolution(n, x);/* 已得到解,输出解 */ ,2020/8/30,主讲教师：四川大学计算机学院 陈良银,24,else for (j = 1;

13、 j = n; j+) /* 第i个皇后所放置的列 */ if(aj=FALSE/* 表示第i个皇后所放 置的位置 */,2020/8/30,主讲教师：四川大学计算机学院 陈良银,25,TrySolution(i + 1, n, a, b, c, x); /* 再试探第i + 1个皇后所放 置的位置 */ /*释放位置(i,j)，进行回溯*/ aj = FALSE; bi + j = FALSE; ci - j + n = FALSE; ,2020/8/30,主讲教师：四川大学计算机学院 陈良银,26,程序动行结果如下：,2020/8/30,主讲教师：四川大学计算机学院 陈良银,27,8.3

14、分而治之方法,分而治之算法就是将大问题划分为小问题，直接解决小问题，或使用递归解决小问题，再将对各个部分的解决组合成对整个问题的解决。下面通过实例加以说明。 例7.4 使用分而治之算法求一个整数数组中的最大数。S7_5.C,2020/8/30,主讲教师：四川大学计算机学院 陈良银,28,将求a0，a1，an-1的最大值max2问题分解为如下两个较小问题： （1）求a0，a1，an-2中的最大值max1; （2）求max1与an-1的最大值max2。 对于问题（1），可用递归解决，对于问题（2）可直接求解。,2020/8/30,主讲教师：四川大学计算机学院 陈良银,29,/* 用分而治之算法求一

15、个整数数组中的最大值 */ int Max(int a, int n) int max1, max2; if (n = 1) /* 递归结束条件成立，结束递归 */ return a0; else /* 递归结束条件不成立，继续递归 */ max1 = Max(a, n - 1); /* 求a0,a1,.,an-1的最 大值max1 */,2020/8/30,主讲教师：四川大学计算机学院 陈良银,30,/* 求max1和an-1的最大值 */ if (max1 an - 1) max2 = max1; else max2 = an-1; return max2; 有很多算法在理论上和实践上都采

16、用分而治之算法，熟悉这种算法对学习后继课程，如数据结构与算法分析将会事半功倍。,2020/8/30,主讲教师：四川大学计算机学院 陈良银,31,程序运行结果如下：,2020/8/30,主讲教师：四川大学计算机学院 陈良银,32,7.5 程序陷阱,1死循环 使用递归函数最常犯的程序陷阱是导致死循环。下面用阶乘的递归定义来说明几种常见的错误。 对于阶乘，如下用递归定义编写的阶乘函数是很很简单的。 int Factorial(int n) if (n = 0) /* 递归结束条件成立，结束递归 */ return 1; else /* 递归结束条件不成立，继续进行递归调用 */ return n *

17、 factorial( n - 1); ,2020/8/30,主讲教师：四川大学计算机学院 陈良银,33,由于n!增长得很快，只对有限的n，函数调用Factorial (n)能产生有效结果。这种类型的编程错误是常见的。如果函数体中的操作超过了系统允许的取值范围，那么尽管它在逻辑上是正确的，也会返回错误的结果。 如果程序员忽略了基本情况而错误地编写了阶乘函数，就会导致死循环。 int Factorial(int n) return n * factorial( n - 1); ,2020/8/30,主讲教师：四川大学计算机学院 陈良银,34,2自减运算符的副作用 另一种虽与与递归不相关，但常见的错误是对自减运算符的错用。在一般递归中都将变量作为参数传递给递归步中函数，