函数II递归解读课件

1、函数II 递归函数II 递归变量的作用域定义在函数内或块内的变量称为局部变量（local variable）。在函数外部定义的变量称为全局变量(global variable)。变量的作用域定义在函数内或块内的变量称为局部变量（local1. 递归的定义什么是递归？说白了就象我们熟悉的那个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说。即递归就是一个对象在定义时用到了自身。这个对象可以是函数、概念、数学结构1. 递归的定义什么是递归？说白了就象我们熟悉的那个民间故事因为故事中包含了故事本身，如果用

2、程序实现，必然是一个对象（函数）直接或间接地调用了其自身。void Story() cout“从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：”; cin.get();/按任意键听下一个故事 Story(); /老和尚讲的故事，实际上就是上面那个故事因为故事中包含了故事本身，如果用程序实现，必然是一个对象（函void Story(int n) if (n MAX) /递归的终止条件 cout从前有座山，山里有座庙，庙里有个老和尚，老和尚对小和尚说了一个故事：; cin.get(); Story(n+1); else cout“都讲”MAX“遍了！你烦不烦哪？n; retu

3、rn ; void Story(int n)递归的特征自己调用自己。直接递归间接递归一定要有递归终止的条件，这个条件通常称为边界条件或递归出口。（注：要确保边界条件能够被执行到）递归的特征自己调用自己。递归的使用场合数据的定义形式按递归定义问题的求解通过子问题来解决递归的使用场合数据的定义形式按递归定义例：求n的阶乘n!（n！= 1*2*n）例：求n的阶乘n!（n！= 1*2*n）分析：我们可以这样定义n!，n!=n(n-1)!，因此求n!转化为求 (n-1)!。这就是一个递归的描述。分析：我们可以这样定义n!，n!=n(n-1)!，因此求n!因此，可以编写如下递归程序： int fac(in

4、t n) if(n=0)return 1;/边界条件 return n*fac(n-1);/else也可 因此，可以编写如下递归程序：下图展示了N=3的执行过程 递归调用示例图下图展示了N=3的执行过程 递归调用示例图由此可知，递归的执行过程分递推和回归两个阶段在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如求n!转化为求(n-1)!,依次类推，直至计算到n=0时。在递推阶段，必须要有终止递归的情况。在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。例如知道0！=1，可以得到1！=1，2！=2，直到n！由此可知，递归的执行过程

5、分递推和回归两个阶段任务：楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，编一程序计算共有多少种不同的走法。任务：楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，【例】 汉诺塔问题。有A、B、C三根柱子，A柱上有n个大小不等的盘子，大盘在下，小盘在上。要求将所有盘子由A柱搬动到C柱上，每次只能搬动一个盘子，搬动过程中可以借助任何一根柱子，但必须满足大盘在下，小盘在上。打印出搬动的步骤。 A柱B柱C柱【例】 汉诺塔问题。有A、B、C三根柱子，A柱上有n个大小不分析：1 A柱只有一个盘子的情况： A柱C柱；2 A柱有两个盘子的情况：小盘A柱B柱，大盘A柱C柱，小盘B柱C柱。3 A柱有n

6、个盘子的情况：将此问题看成上面n-1个盘子和最下面第n个盘子的情况。n-1个盘子A柱B柱，第n个盘子A柱C柱，n-1个盘子B柱C柱。问题转化成搬动n-1个盘子的问题，同样，将n-1个盘子看成上面n-2个盘子和下面第n-1个盘子的情况，进一步转化为搬动n-2个盘子的问题，类推下去，一直到最后成为搬动一个盘子的问题。这是一个典型的递归问题，递归结束于只搬动一个盘子。函数的递归调用分析：函数的递归调用算法可以描述为：1 n-1个盘子A柱B柱，借助于C柱；2 第n个盘子A柱C柱；3 n-1个盘子B柱C柱，借助于A柱；其中步骤1和步骤3继续递归下去，直至搬动一个盘子为止。由此，可以定义两个函数，一个是递

7、归函数，命名为hanoi(int n, char source, char temp, char target)，实现将n个盘子从源柱source借助中间柱temp搬到目标柱target；另一个命名为move(char source, char target)，用来输出搬动一个盘子的提示信息。算法可以描述为：程序如下：#include void move(char source,char target) coutsourcetargetendl;void hanoi(int n,char source,char temp,char target) if(n=1) move(source,tar

8、get); elsehanoi(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);程序如下：任务：用辗转相除法求最大公约数任务：用辗转相除法求最大公约数任务：输入一个整数，用递归算法将整数倒序输出。任务：输入一个整数，用递归算法将整数倒序输出。N皇后问题N皇后问题在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一

9、列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法。 八皇后的两组解N皇后问题N皇后问题在N*N的棋盘上放置N个皇后而彼此不受分析： 由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置都要进行试探和纠正(“回溯”思想）。在N个皇后未放置完成前，摆放第I个皇后和第I+1个皇后的试探方法是相同的，因此完全可以采用递归的方法来处理。分析：下面是放置第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个皇后的的递归算法(伪代码)：一维数组实现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;int check(int