资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,函数II 递归,函数II 递归,1,变量的作用域,定义在函数内或块内的变量称为,局部变量（local variable）。,在函数外部定义的变量称为,全局变量(global variable),。,变量的作用域定义在函数内或块内的变量称为局部变量（local,2,1. 递归的定义,什么是递归？说白了就象我们熟悉的那个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说。,即递归就是一个对象在定义时用到了自身。,这个对象可以是函数、概念、数学结构,1. 递归的定义什么是递归？说白了就象我们熟悉的那个民间故事,3,因为故事中包含了故事本身，如果用程序实现，,必然是一个对象（函数）,直接或间接地调用了其自身。,void Story(),cout“从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：”;,cin.get();/按任意键听下一个故事,Story(); /老和尚讲的故事，实际上就是上面那个故事,因为故事中包含了故事本身，如果用程序实现，必然是一个对象（函,4,void Story(int n),if (n MAX),/递归的终止条件,cout从前有座山，山里有座庙，庙里有个老和尚，老和尚对小和尚说了一个故事：;,cin.get();,Story(n+1);,else,cout“都讲”MAX“遍了！你烦不烦哪？n;,return ;,void Story(int n),5,递归的特征,自己调用自己。,直接递归,间接递归,一定要有递归终止的条件，这个条件通常称为边界条件或递归出口。（注：,要确保边界条件能够被执行到,）,递归的特征自己调用自己。,6,递归的使用场合,数据的定义形式按递归定义,问题的求解通过子问题来解决,递归的使用场合数据的定义形式按递归定义,7,例：求n的阶乘n!（n！= 1*2*n）,例：求n的阶乘n!（n！= 1*2*n）,8,分析：我们可以这样定义n!，n!=n(n-1)!，因此求n!转化为求 (n-1)!。这就是一个递归的描述。,分析：我们可以这样定义n!，n!=n(n-1)!，因此求n!,9,因此，可以编写如下递归程序：,int fac(int n),if(n=0)return 1;/边界条件,return,n*fac(n-1);/else也可,因此，可以编写如下递归程序：,10,下图展示了N=3的执行过程,递归调用示例图,下图展示了N=3的执行过程 递归调用示例图,11,由此可知，递归的执行过程分递推和回归两个阶段,在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如求n!转化为求(n-1)!,依次类推，直至计算到n=0时。在递推阶段，必须要有终止递归的情况。,在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。例如知道0！=1，可以得到1！=1，2！=2，直到n！,由此可知，递归的执行过程分递推和回归两个阶段,12,任务：楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，编一程序计算共有多少种不同的走法。,任务：楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，,13,【例】,汉诺塔问题。,有,A,、,B,、,C,三根柱子，,A,柱上有,n,个大小不等的盘子，大盘在下，小盘在上。要求将所有盘子由,A,柱搬动到,C,柱上，每次只能搬动一个盘子，搬动过程中可以借助任何一根柱子，但必须满足大盘在下，小盘在上。打印出搬动的步骤。,A柱,B柱,C柱,【例】 汉诺塔问题。有A、B、C三根柱子，A柱上有n个大小不,14,分析：,1 A柱只有一个盘子的情况： A柱,C柱；,2 A柱有两个盘子的情况：小盘A柱,B柱，大盘A柱,C柱，小盘B柱,C柱。,3 A柱有n个盘子的情况：将此问题看成上面n-1个盘子和最下面第n个盘子的情况。n-1个盘子A柱,B柱，第n个盘子A柱,C柱，n-1个盘子B柱,C柱。问题转化成搬动n-1个盘子的问题，同样，将n-1个盘子看成上面n-2个盘子和下面第n-1个盘子的情况，进一步转化为搬动n-2个盘子的问题，类推下去，一直到最后成为搬动一个盘子的问题。,这是一个典型的递归问题，递归结束于只搬动一个盘子。,函数的递归调用,分析：函数的递归调用,15,算法可以描述为：,1 n-1个盘子A柱,B柱，借助于C柱；,2 第n个盘子A柱,C柱；,3 n-1个盘子B柱,C柱，借助于A柱；,其中步骤1和步骤3继续递归下去，直至搬动一个盘子为止。由此，可以定义两个函数，一个是递归函数，命名为hanoi(int n, char source, char temp, char target)，实现将n个盘子从源柱source借助中间柱temp搬到目标柱target；另一个命名为move(char source, char target)，用来输出搬动一个盘子的提示信息。,算法可以描述为：,16,程序如下：,#include ,void move(char source,char target),couttargetendl;,void hanoi(int n,char source,char temp,char target),if(n=1) move(source,target);,else,hanoi(n-1,source,target,temp);,/将n-1个盘子搬到中间柱,move(source,target);,/将最后一个盘子搬到目标柱,hanoi(n-1,temp,source,target);,/将n-1个盘子搬到目标柱,void main(),int n;,cout输入盘子数：n;,hanoi(n,A,B,C);,程序如下：,17,任务：用辗转相除法求最大公约数,任务：用辗转相除法求最大公约数,18,任务：输入一个整数，用递归算法将整数倒序输出。,任务：输入一个整数，用递归算法将整数倒序输出。,19,N皇后问题,N皇后问题在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法。,八皇后的两组解,N皇后问题N皇后问题在N*N的棋盘上放置N个皇后而彼此不受,20,分析：,由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置都要进行试探和纠正(“回溯”思想）。在N个皇后未放置完成前，摆放第I个皇后和第I+1个皇后的试探方法是相同的，因此完全可以采用递归的方法来处理。,分析：,21,下面是放置第I个皇后的的递归算法(伪代码)：,void put(int i) /搜索第i行皇后的位置,if (i=n+1) 输出方案；/递归出口,for（int j=1;j=n;j+）/枚举各种可能，纠正,if (皇后能放在第i行第j列的位置),在第i行第j列放置第i个皇后；/试探,put（i+1）；/化成和原来相同的子问题,抹去第i行第j列放置的皇后；/纠正,下面是放置第I个皇后的的递归算法(伪代码)：,22,一维数组实现,int mapmaxn+1=0;,Int usedmaxn+1=0;,void put(int i),if (i=n+1) print（）；,for（int j=1;j=n;j+）,if (usedj&check(i,j),mapi=j；/试探,put（i+1）；/化成和原来相同的子问题,void main(),getinfo();,put(1);,一维数组实现int mapmaxn+1=0;,23,int check(int i,int j),for(int k=1;kI;k+),if(k-i)=abs(mapk-j) return 0;,return 1;,void print(),for(int i=1;i=n;i+),foutmapi;,if(in) fout ;,foutendl;,int check(int i,int j),24,
展开阅读全文