函数的递归调用 函数的递归调用 递归递归: 一个函数直接或间接地使用自身。一个函数直接或间接地使用自身。 1. 直接递归调用：直接递归调用：函数直接调用本身函数直接调用本身 2. 间接递归调用：间接递归调用：函数间接调用本身函数间接调用本身情景情景1：小时候，我们听过这样的故事：小时候，我们听过这样的故事：从前有座山，山上有座庙，庙里有个老和尚给小和尚讲故从前有座山，山上有座庙，庙里有个老和尚给小和尚讲故事，讲的什么事，讲的什么故事故事呢？呢？从前有座山，山上有座庙，庙里有从前有座山，山上有座庙，庙里有个老和尚给小和尚讲故事，讲的什么个老和尚给小和尚讲故事，讲的什么故事故事呢？呢？从前有座山，从前有座山，山上有座庙，庙里有个老和尚给小和尚讲故事，讲的什么山上有座庙，庙里有个老和尚给小和尚讲故事，讲的什么故事呢？故事呢？故事可以一直讲下去，每一个故事内容都相同，但却是故事里的故事。程序设计中，函数A自己调用自己，称为直接直接递归调用递归调用。情景情景2：镜子镜子A和镜子和镜子B相对放在一起，你会发现什么相对放在一起，你会发现什么现象呢？现象呢？对了，我们会发现镜子对了，我们会发现镜子A A中有镜子中有镜子B B的映象，镜子的映象，镜子B B中又镜子中又镜子A A的映象，这的映象，这样层层叠叠，无穷无尽。样层层叠叠，无穷无尽。AB在程序设计中，像这种函数A调用函数B,函数B再反过来调用函数A的算法，称为间接间接递归调用递归调用。 递归算法的特点：递归函数的执行过程比较复杂，往往都存在着连续的递归调用，其执行过程可分为 “递推” 和 “回归” 两个阶段，先是一次一次不断的递推过程，直到符合递推”结束条件，然后是一层一层的回归过程。 而其中的每一次递归调用，系统都要在栈中分配空间以保存该次调用的返回地址、 参数、局部变量，因此在递推阶段，栈空间一直处于增长状态， 然后进入回归阶段，栈空间反向依次释放。 直到“递推” 过程的终止， 在递归的执行过程中，递归结束条件非常重要，它控制 “递推” 过程的终止，在任何一个递归函数中，递归结束条件都是必不可少的， 否则将会一直 “递推” 下去。导致无穷递归。递归算法的缺点：内存消耗巨大，且连续地调用和返回操作占用较多的CPU时间。 递归算法的优点：算法描述简洁易懂。 思考如下问题：思考如下问题：例例1: 有有5个人坐在一起个人坐在一起,问第问第5个人多少岁个人多少岁,他说比第他说比第4个人大个人大2岁岁;问第问第4个人岁数个人岁数,他说比他说比第第3个人大个人大2岁岁;问第问第3个人个人,又说比第又说比第2个大个大2岁岁;问第问第2个人，说比第个人，说比第1个人大个人大2岁；最后问第岁；最后问第1个人，他说他个人，他说他10岁；请问第岁；请问第5个人多大个人多大?比她大比她大2岁岁比她大比她大2岁岁比她大比她大2岁岁比她大比她大2岁岁我我10岁岁分析分析：要求第：要求第5个人的年龄，就必须先知道第个人的年龄，就必须先知道第4个人的年龄，而第个人的年龄，而第4个人个人的年龄也不知道，要求第的年龄也不知道，要求第4个人的年龄必须先知道第个人的年龄必须先知道第3个人的年龄，而个人的年龄，而第第3个人的年龄又取决于第个人的年龄又取决于第2个人的年龄，第个人的年龄，第2个人的年龄取决于第个人的年龄取决于第1个个人的年龄。而且每一个人的年龄都比其前人的年龄。而且每一个人的年龄都比其前1个人的年龄大个人的年龄大2。第一个人。第一个人的年龄已知，根据第一个人的年龄可依次求得第二、三、四、五个人的年龄已知，根据第一个人的年龄可依次求得第二、三、四、五个人的年龄。这就是一个递归问题。的年龄。这就是一个递归问题。而而每一个人的年龄都比其前每一个人的年龄都比其前1个人的年龄大个人的年龄大2 就是递归成立的条件，也就就是递归成立的条件，也就是是递归公式递归公式。age（5）=age（4）2 age（4）=age（3）2 age（3）=age (2）+2 age（2）age(1）2 age（1）10 可以用式子表述如下：可以用式子表述如下： age（n）=10 （n=1） age（n）= age（n-1)+2 （n1）可以看到，当可以看到，当n1时，求第时，求第n个人的年龄的公式是相同的。因此可以用个人的年龄的公式是相同的。因此可以用一个函数来表示上述关系，下图表示求第一个函数来表示上述关系，下图表示求第5个人年龄的过程。个人年龄的过程。 age(5) age(5) age(5) age(5) =age(4)+2 =18 =age(4)+2 =18 age(4) age(4) age(4) age(4) =age(3)+2 =16 =age(3)+2 =16 age(3) age(3) age(3) age(3) =age(2)+2 =14 =age(2)+2 =14 age(2) age(2) age(2) age(2) =age(1)+2 = 12 =age(1)+2 = 12 age(1) age(1) =10 =10 回回推推递递推推 从图可知，求解可分成两个阶段：第一阶段是从图可知，求解可分成两个阶段：第一阶段是“ “回回推推” ”，即将第，即将第n n个人的年龄表示为第（个人的年龄表示为第（n-1n-1）个人年）个人年龄的函数，而第（龄的函数，而第（n n一一1 1）个人的年龄仍然不知道，）个人的年龄仍然不知道，还要还要“ “回推回推” ”到第（到第（n n一一2 2）个人的龄）个人的龄，直到第，直到第1 1个人的年龄。此时个人的年龄。此时age(1)age(1)已知，不必再向前推了。已知，不必再向前推了。然后开始第二阶段，采用然后开始第二阶段，采用递推递推递推递推方法，从第方法，从第1 1个人的个人的已知年龄推算出第已知年龄推算出第2 2个人的年龄（个人的年龄（1212岁），从第岁），从第2 2个个人的年龄推算出人的年龄推算出3 3个人的年龄（个人的年龄（1414岁）岁），一直推，一直推算出第算出第5 5个人的年龄（个人的年龄（1818岁）为止。也就是说，一岁）为止。也就是说，一个递归的题可以分为个递归的题可以分为“回推回推回推回推”和和和和“递推递推”两个阶两个阶段。要经历许多步才能求出最后的值。显而易见，段。要经历许多步才能求出最后的值。显而易见，如果求递归过程不是无限制进行下去，必须具有一如果求递归过程不是无限制进行下去，必须具有一个结束递归过程的条件。个结束递归过程的条件。 例如，例如，ageage（1 1）1010，就是递归结束的条件。，就是递归结束的条件。 可以用一个函数来描述上述递归过程：可以用一个函数来描述上述递归过程： age age（n n） /* /*求年龄的递归函数求年龄的递归函数求年龄的递归函数求年龄的递归函数* * int n int n；int cint c； * * c c用来存放函数的返回值用来存放函数的返回值用来存放函数的返回值用来存放函数的返回值 if if（n= =1n= =1） c=10;c=10; else c=age else c=age（n n一一一一1 1）十）十）十）十2 2； return return（c)c)； main main（）（）（）（）/* /*主函数主函数主函数主函数* * printf printf（%d%d，ageage（5 5）；）；）；）； 例题二例题二 用递归方法求用递归方法求n! 分析：假设分析：假设n=5 我们知道我们知道 5！=1*2*3*4*5=4！*5 4！=1*2*3*4=3！*4 3！=1*2*3=2！*3 2！=1*2=1！*2 1！=1 可用下面的递归公式表示可用下面的递归公式表示 n!=1 （n=1） n!=(n-1)!*n (n 1)“回推”和“递推”5！54！43！32！21！15！4！53！42！31！21回推过程返回1返回1！22返回2！36返回3！424返回4！5120终值120递推过程调用函数函数返回值 递归法求递归法求Fibonacci数列数列 Fibonacci数列数列: 1, 1, 2, 3, 5, 8, 13 迭代法求迭代法求Fibonacci数列的前数列的前20项项 #include void main( ) int i , f1=1 , f2=1 , f3; printf(“%8d%8d”, f1 , f2); for ( i=3 ; i1 F(n)=递归的终止条件递归的终止条件递归公式递归公式int Fib(int n) if (n0) printf(“error!”); exit(-1); else if (n 1）个盘子的汉诺塔，可分为三个步骤求解：1.将A针上n-1个盘子借助于C针移到B针 2.把A针上剩下的一个盘子移到C针 3.将B针上n-1个盘子借助于A针移到C针 显然，上述1,3两步具有与原问题相同的性质，只是在问题的规模上比原问题有所缩小，可用递归实现。 整理上述分析结果，把第一步作为递归结束条件，将第二步分析得到的算法作为递归算法，可以写出如下完整的递归算法描述： 定义一个函数movedisk (int n,char fromneedle ,char tempneedle , char toneedle )，该函数的功能是将fromneedle针上的n个盘子借助于tempneedle针移动到toneedlee针，这样移动n个盘子的递归算法描述如下： movedisk(int n,char fromneedle,char tempneedle,char toneedle) if (n=1) 将n号盘子从one针移到three针; esle 1. movedisk(n-1 , fromneedle , toneedle , tempneedle) 2.将n号盘子从fromneedle针移到toneedle针; 3. movedisk(n-1, tempneedle, fromneedle, toneedle) 按照上述算法可编写出如下C语言程序： #include void main() void movedisk(int n,char fromneedle,char tempneedle,char toneedle); int n; printf (“Pleases input the number of diskes:”); scanf(“%d”,&n); printf (“The step moving diskes is:n”); movedisk (n,A,B,C); void movedisk(int n,char fromneedle,char tempneedle,char toneedle) if (n=1) printf (“%c%cn”,fromneedle,toneedle ); else movedisk(n-1,fromneedle,toneedle,tempneedle ); printf (“%c%cn”,fromneedle,toneedle ); movedisk (n-1,tempneedle,fromneedle,toneedle ); 以N=3为例BCA以N=3为例第一步：A CBCA以N=3为例第二步：A BBCA以N=3为例第三步：CBBCA以N=3为例第四步：ACBCA以N=3为例第五步：BABCA以N=3为例第六步：BCBCA以N=3为例第七步：ACBCA八皇后问题问题描述：问题描述： 会下国际象棋的人都很清楚：皇后可以在横竖斜线上不限步数地吃掉其会下国际象棋的人都很清楚：皇后可以在横竖斜线上不限步数地吃掉其他棋子，如何将他棋子，如何将8 8个皇后放在棋盘上（有个皇后放在棋盘上（有8*88*8个方格），使他们谁也不能个方格），使他们谁也不能被吃掉！这就是著名的八皇后问题。对于某个满足要求的被吃掉！这就是著名的八皇后问题。对于某个满足要求的8 8皇后的摆放方皇后的摆放方法，定义一个皇后串法，定义一个皇后串a a与之对应，即与之对应，即a=b1b2a=b1b2b8b8，其中，其中bibi为相应摆法中第为相应摆法中第i i行皇后所处的列数。已经知道行皇后所处的列数。已经知道8 8皇后问题一共有皇后问题一共有9292组解（即组解（即9292个、不同个、不同的皇后串）。给出一个数的皇后串）。给出一个数b b，要求输出第，要求输出第b b个串。串的比较是这样的：皇个串。串的比较是这样的：皇后串后串x x置于皇后串置于皇后串y y之前，当且仅当将之前，当且仅当将x x视为整数时比视为整数时比y y小。小。输入数据：输入数据： 第一行是测试数据的组数第一行是测试数据的组数n n，后面跟着，后面跟着n n行输入，每组测试数据占行输入，每组测试数据占1 1行，包行，包括一个正整数括一个正整数b b（1=b=921=b=92）。）。输出要求：输出要求：n n行，每行输出对应一个输入。输出应是一个正整数，是对应于行，每行输出对应一个输入。输出应是一个正整数，是对应于b b的皇后串。的皇后串。输入样例：输入样例：2 21 19292输出样例：输出样例：1586372415863724解题思路：解题思路：1 1、因为要求出、因为要求出9292中不同的摆放方法中的任意一种，所有我们不妨把中不同的摆放方法中的任意一种，所有我们不妨把9292中不同的中不同的摆放方法一次性求出来，存放在一个数组里。为求解这道题我们需要一个矩摆放方法一次性求出来，存放在一个数组里。为求解这道题我们需要一个矩阵仿真棋盘，每次试放一个棋子时只能放在尚未被控制的格子上，一旦放置阵仿真棋盘，每次试放一个棋子时只能放在尚未被控制的格子上，一旦放置了一个新棋子，就在它所能控制的所有位置上设置标记，如此下去把八个棋了一个新棋子，就在它所能控制的所有位置上设置标记，如此下去把八个棋子放好。完成一种摆放时，就要尝试下一种。若要按照字典序将可行摆放方子放好。完成一种摆放时，就要尝试下一种。若要按照字典序将可行摆放方法记录下来，就要按照一定的顺序进行尝试。也就是将第一个棋子按照从小法记录下来，就要按照一定的顺序进行尝试。也就是将第一个棋子按照从小到大的顺序尝试，对于第一个棋子的位置，将第二个棋子从可行的位置从小到大的顺序尝试，对于第一个棋子的位置，将第二个棋子从可行的位置从小到大的顺序尝试；在第一和第二个棋子固定的情况下，将第三个棋子从可行到大的顺序尝试；在第一和第二个棋子固定的情况下，将第三个棋子从可行的位置从小到大的顺序尝试；以此类推。的位置从小到大的顺序尝试；以此类推。2 2、首先，我们有一个、首先，我们有一个8*88*8的矩阵仿真棋盘标识当前已经摆好的棋子所控制的区域。的矩阵仿真棋盘标识当前已经摆好的棋子所控制的区域。用一个用一个9292行每行行每行8 8个元素的二维数组记录可行的摆放方法。用一个递归程序实个元素的二维数组记录可行的摆放方法。用一个递归程序实现尝试摆放的过程。基本思想就是假设我们将第一个棋子摆好，并设置它的现尝试摆放的过程。基本思想就是假设我们将第一个棋子摆好，并设置它的控制区域，则这个问题就变成了一个控制区域，则这个问题就变成了一个7 7皇后问题，用与皇后问题，用与8 8皇后同样的方法可以皇后同样的方法可以获得问题的求解。那我们就把重心放在如何摆放一个皇后棋子上，摆放的基获得问题的求解。那我们就把重心放在如何摆放一个皇后棋子上，摆放的基本步骤是：从第本步骤是：从第1 1到第到第8 8个位置，顺序地尝试将棋子放置在每一个未被控制的个位置，顺序地尝试将棋子放置在每一个未被控制的位置，设置该棋子所控制的格子，将问题变成更小规模的问题向下递归，需位置，设置该棋子所控制的格子，将问题变成更小规模的问题向下递归，需要注意的是每次尝试一个新的未被控制的位置前，要将上一次尝试的位置所要注意的是每次尝试一个新的未被控制的位置前，要将上一次尝试的位置所控制的格子复原。控制的格子复原。#include #include int queenPlaces928; int count=0; int board88; void putQueen(int ithQueen);/递归函数void main() int n,i,j; for(i=0;i8;i+) for(j=0;i8;j+) boardij=-1; for(j=0;j92;j+) queenPlacesji=0; putQueen(0);/从第0个棋子开始摆放 scanf(“%d”,&n); for(i=0;in;i+) int ith; scanf(“%d”,&ith) for(j=0;j8;j+) printf(“%d”,queenPlacesithj); printf(“n”); void putQueen(int ithQueen) int i,k,r; if (ithQueen=8) count+; return; for(i=0;i8;i+) if(boardiithQueen=-1) boardiithQueen=ithQueen; /摆放皇后 /将其后所有的摆放方法的ith个皇后都放在i+1的位置上 /将i增加后，后面的第ith个皇后摆放方法后覆盖此时的设置 for(k=count;k92;k+) queenPlaceskithQueen=i+1; /设置控制范围 for(k=0;k8;k+) for(r=0;r8;r+) if(boardkr=-1)& (k=i|r=ithQueen|abs(k-i)=abs(r-ithQueen) boardkr=ithQueen; /向下级递归putQueen(ithQueen+1); /回溯，撤销控制范围for(k=0;k8;k+) for(r=0;r8;r+) if(boardkr=ithQueen)boardkr=-1;