主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章主讲教师：*个人主页：*2024/9/181主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章教材：教材：C语言程序设计（语言程序设计（C99版）版）陈良银陈良银 游洪跃游洪跃 李旭伟李旭伟 主编主编李志蜀李志蜀 唐宁九唐宁九 李李 涛涛 主审主审清华大学出版社清华大学出版社2006年年9月出版月出版2024/9/182主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章本书本书内容内容 2024/9/183主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章分而治之方法分而治之方法本章主要内容本章主要内容ARM Vector TableFIQIRQ(Reserved)Data AbortPrefetch AbortSoftware InterruptUndefined InstructionReset0x1C0x180x140x100x0C0x080x040x001 13 32 2回溯法回溯法递归问题求解递归问题求解2024/9/184主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章本章的节本要求本章的节本要求本章主要介绍本章主要介绍C语言的语言的递归方法递归方法，通过，通过本章的学习使读者了解各种常见的递本章的学习使读者了解各种常见的递归方法，通编写基本的递归程序。归方法，通编写基本的递归程序。 本章将主要介绍两种递归方法：本章将主要介绍两种递归方法：回溯回溯法法和和分而治之方法分而治之方法。 在网页：在网页：http:/cs.scu.edu.cn/youhongyao可获得可获得源代码源代码等相关资源。等相关资源。2024/9/185主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章7.1 递归问题求解递归问题求解递归是函数直接或间接对自已进行调递归是函数直接或间接对自已进行调用，在用，在C语言中，所有函数都可以使用语言中，所有函数都可以使用递归，数学上的迭代函数都可以用递递归，数学上的迭代函数都可以用递归进行编程。归进行编程。例例7.1 用递归求阶乘用递归求阶乘n!S7_1.C。阶乘可用迭代表示如下：阶乘可用迭代表示如下：2024/9/186主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章/* 用递归求阶乘用递归求阶乘n! */int Factorial(int n)if (n = 0)/* 递归结束条件成立，结束递归递归结束条件成立，结束递归 */return 1;else/* 递归结束条件不成立，继续进行递归递归结束条件不成立，继续进行递归调用调用 */return n * Factorial( n - 1);2024/9/187主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章下面对下面对递归函递归函数数factorial()进行进行分析，分析，可以先可以先考虑基考虑基本情况，本情况，然后再然后再由基本由基本情况推情况推算其他算其他情况情况 函数调用返回值factorial(0)1factorial(1)1* factorial(0)，即1*1factorial(2)2* factorial(1)，即2*1*1factorial(3)3* factorial(2)，即3*2*1*1factorial(4)4* factorial(3)，即4*3*2*1*1factorial(5)5* factorial(4)，即5*4*3*2*1*1factorial(6)6* factorial(5)，即6*5*4*3*2*1*12024/9/188主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章简单递归通常都有对函数的入口进行简单递归通常都有对函数的入口进行测试的基本情况。测试的基本情况。2024/9/189主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章一般递归具有如下的一般递归具有如下的两种形式两种形式：形式形式1if () /*递归结束条件成立，结束递归调用递归结束条件成立，结束递归调用 */递归结束处理方面的语句递归结束处理方面的语句;else /*递归结束条件不成立，继续进行递归调用递归结束条件不成立，继续进行递归调用 */递归调用方面的语句递归调用方面的语句;2024/9/1810主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章形式形式2if () /* 递归调用条件成立，继续进行递归调用递归调用条件成立，继续进行递归调用 */递归调用方面的语句递归调用方面的语句;else /* 递归调用条件不成立，结束递归调用递归调用条件不成立，结束递归调用 */递归结束处理方面的语句递归结束处理方面的语句;2024/9/1811主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章例例7.2 用递归实现将输入的一行字符串按用递归实现将输入的一行字符串按逆逆序序重新输出。重新输出。S7_2.C/* 将输入的一行字符串按逆序重新输出的递归函数将输入的一行字符串按逆序重新输出的递归函数 */void ReverseDisplay(void)int c;if (c = getchar() != n)/* 递归调用条件成立时，继续递归调用递归调用条件成立时，继续递归调用 */ReverseDisplay();putchar(c);2024/9/1812主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章下面对程序代码进行分析：下面对程序代码进行分析：printf(输入一行字符串输入一行字符串:n);ReverseDisplay ();向用户提示后，进行递归调用函数向用户提示后，进行递归调用函数ReverseDisplay ()，当户用按回车键后终止输入。当户用按回车键后终止输入。if (c=getchar() != n)ReverseDisplay ();用户每输入一个字符，只要没按回车键，都会启用户每输入一个字符，只要没按回车键，都会启动一次对动一次对ReverseDisplay()的调用，这时的内部变的调用，这时的内部变量量c都有自已的存储空间，用于存储所输入的字符，都有自已的存储空间，用于存储所输入的字符，每次调用所输入的字符被堆叠起来，直到按回车每次调用所输入的字符被堆叠起来，直到按回车键为止。键为止。2024/9/1813主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章putchar(c);当用户输入一行后，才开始显示字符，当用户输入一行后，才开始显示字符，每次调用每次调用ReverseDisplay()都显示存储都显示存储在内部变量在内部变量c中的值，显示顺序是先显中的值，显示顺序是先显示回车符示回车符n，再显示换行前的最后再显示换行前的最后一个字符，这样下去，直到显示第一一个字符，这样下去，直到显示第一个字符为止，这样便实现了输入字符个字符为止，这样便实现了输入字符串的逆序显示。串的逆序显示。2024/9/1814主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章例例7.3 修改例修改例7.2，用递归实现将输入的，用递归实现将输入的一行文本一行文本按词逆序按词逆序重新输出。重新输出。 S7_3.C将例将例7.2中的中的getchar()改成接收单词的改成接收单词的函数函数get_word()，并用函数返回单词的并用函数返回单词的下一个字符下一个字符（如空格符或回车符）（如空格符或回车符） 2024/9/1815主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章void ReverseDisplay(void)char wMAXWORD;if (GetWord(w) != n)ReverseDisplay();printf(%s , w);2024/9/1816主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章/* 输入一个单词输入一个单词,用用s返回所输入的单词返回所输入的单词,函函数返回值为所输入单词的下一个字符数返回值为所输入单词的下一个字符 */ int GetWord(char *s)int c;while (c = getchar() != & c != n)/* 输入单词输入单词 */*s+ = (char)c;*s = 0; return c;2024/9/1817主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章运行程序时，如果用户输入运行程序时，如果用户输入“this is a string .”，运行界面如下所示：运行界面如下所示： 2024/9/1818主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章8.2回溯法回溯法假假设设问问题题的的解解为为 n 元元组组 (x1, x2, , xn)，其其中中 xi取取值值于于集集合合Seti，n元元组组的的子子组组 (x1, x2, , xi) (i n)/ 已求得解已求得解 输出当前解输出当前解;2024/9/1820主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章else / 回溯求解回溯求解 for (all xi Seti) 修改解的第修改解的第i个元素为个元素为xi; if (x1, x2, , xi)满足约束条件满足约束条件) / 继续求下一个部分解继续求下一个部分解 BackTracking(i + 1, n); 恢复解未修改前的状况恢复解未修改前的状况;/回溯求新的解回溯求新的解 2024/9/1821主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章例例7.4皇后问题求解：在皇后问题求解：在nn棋盘上放棋盘上放置置n个皇后，这些皇后中任意两个皇后个皇后，这些皇后中任意两个皇后不能在同一行，同一列，同一条对角不能在同一行，同一列，同一条对角线（包括主，次对角线）线（包括主，次对角线）。如有解则。如有解则输出所有合法的解。输出所有合法的解。 S7_4.C2024/9/1822主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章/*前前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);/* 已得到解已得到解,输出解输出解 */2024/9/1823主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章elsefor (j = 1; j an - 1)max2 = max1;elsemax2 = an-1;return max2;有很多算法在理论上和实践上都采用分而治之有很多算法在理论上和实践上都采用分而治之算法，熟悉这种算法对学习后继课程，如数据算法，熟悉这种算法对学习后继课程，如数据结构与算法分析将会事半功倍。结构与算法分析将会事半功倍。 2024/9/1830主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章程序运行结果如下：程序运行结果如下： 2024/9/1831主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章7.5 程序陷阱程序陷阱1死循环死循环使用递归函数最常犯的程序陷阱是导致死循环。使用递归函数最常犯的程序陷阱是导致死循环。下面用阶乘的递归定义来说明几种常见的错误。下面用阶乘的递归定义来说明几种常见的错误。对于阶乘，如下用递归定义编写的阶乘函数是很对于阶乘，如下用递归定义编写的阶乘函数是很很简单的。很简单的。int Factorial(int n)if (n = 0)/* 递归结束条件成立，结束递归递归结束条件成立，结束递归 */ return 1;else/* 递归结束条件不成立，继续进行递归调用递归结束条件不成立，继续进行递归调用 */ return n * factorial( n - 1);2024/9/1832主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章由于由于n!增长得很快，只对有限的增长得很快，只对有限的n，函数调函数调用用Factorial (n)能产生有效结果。这种类型能产生有效结果。这种类型的编程错误是常见的。如果函数体中的操作的编程错误是常见的。如果函数体中的操作超过了系统允许的取值范围，那么尽管它在超过了系统允许的取值范围，那么尽管它在逻辑上是正确的，也会返回错误的结果。逻辑上是正确的，也会返回错误的结果。如果程序员忽略了基本情况而错误地编写了如果程序员忽略了基本情况而错误地编写了阶乘函数，就会导致阶乘函数，就会导致死循环死循环。int Factorial(int n)return n * factorial( n - 1);2024/9/1833主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章2自减运算符的副作用自减运算符的副作用另一种虽与与递归不相关，但常见的错误是对自另一种虽与与递归不相关，但常见的错误是对自减运算符的错用。在一般递归中都将变量作为参减运算符的错用。在一般递归中都将变量作为参数传递给递归步中函数，假设变量是数传递给递归步中函数，假设变量是n，它逐渐减它逐渐减小。对于一些算法，小。对于一些算法，-n是正确的参数，而对于另是正确的参数，而对于另一些算法则是不正确的。清考虑如下的代码：一些算法则是不正确的。清考虑如下的代码：int Factorial(int n)if (n = 0) /* 递归结束条件成立，结束递归递归结束条件成立，结束递归 */return 1;else /* 递归结束条件不成立，继续进行递归调用递归结束条件不成立，继续进行递归调用 */return n * factorial(-n);两次用了变量两次用了变量n。由于自减运算符有副作用，第二由于自减运算符有副作用，第二个个n可能影响第一个可能影响第一个n的值。这种类型的编程错误的值。这种类型的编程错误是常见的。是常见的。2024/9/1834主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银 主主编编： 陈陈良良银银 游游洪洪跃跃 李李旭旭伟伟 四四川川大大学学计计算算机机学学院院 C C语语言言程程序序设设计计（ C C9 99 9版版） 清华大学出版社第七章ThankThanks!s! 2024/9/1835主讲教师：四川大学计算机学院主讲教师：四川大学计算机学院 陈良陈良银银