1、函数II 递归变量的作用域 定义在函数内或块内的变量称为定义在函数内或块内的变量称为局部变量局部变量（local variable）。）。在函数外部定义的变量称为在函数外部定义的变量称为全局变量全局变量(global variable)。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;return;递归的特征 自己调用自己。直接递归 间接递归 一定要有递归终止的条件，这个条件通常称为边界条件或递归出口。（注：要确保边界条件能够被
3、执行到）递归的使用场合 数据的定义形式按递归定义 问题的求解通过子问题来解决 例：求n的阶乘n!（n！=1*2*n）分析：我们可以这样定义n!，n!=n(n-1)!，因此求n!转化为求(n-1)!。这就是一个递归的描述。010)!1(*!nnnnn 因此，可以编写如下递归程序：int fac(int n)if(n=0)return 1;/边界条件 return n*fac(n-1);/else也可 下图展示了N=3的执行过程 递归调用示例图递归调用示例图 由此可知，递归的执行过程分递推和回归两个阶段 在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例
4、如求n!转化为求(n-1)!,依次类推，直至计算到n=0时。在递推阶段，必须要有终止递归的情况。在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。例如知道0！=1，可以得到1！=1，2！=2，直到n！任务：楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，编一程序计算共有多少种不同的走法。【例例】汉诺塔问题。汉诺塔问题。有有A、B、C三根柱子，三根柱子，A柱上有柱上有n个大小不等的盘子，大盘在下，小盘在上。要求将所有个大小不等的盘子，大盘在下，小盘在上。要求将所有盘子由盘子由A柱搬动到柱搬动到C柱上，每次只能搬动一个盘子，搬柱上，每次只能搬动一个盘子，搬动过程中可以借助
5、任何一根柱子，但必须满足大盘在下，动过程中可以借助任何一根柱子，但必须满足大盘在下，小盘在上。打印出搬动的步骤。小盘在上。打印出搬动的步骤。A柱柱B柱柱C柱柱分析：分析：1 A1 A柱只有一个盘子的情况：柱只有一个盘子的情况：A A柱柱C C柱；柱；2 A2 A柱有两个盘子的情况：小盘柱有两个盘子的情况：小盘A A柱柱B B柱，大盘柱，大盘A A柱柱C C柱，柱，小盘小盘B B柱柱C C柱。柱。3 A3 A柱有柱有n n个盘子的情况：将此问题看成上面个盘子的情况：将此问题看成上面n-1n-1个盘子和个盘子和最下面第最下面第n n个盘子的情况。个盘子的情况。n-1n-1个盘子个盘子A A柱柱B
6、B柱，第柱，第n n个盘个盘子子A A柱柱C C柱，柱，n-1n-1个盘子个盘子B B柱柱C C柱。问题转化成搬动柱。问题转化成搬动n-1n-1个盘子的问题，同样，将个盘子的问题，同样，将n-1n-1个盘子看成上面个盘子看成上面n-2n-2个盘子个盘子和下面第和下面第n-1n-1个盘子的情况，进一步转化为搬动个盘子的情况，进一步转化为搬动n-2n-2个盘个盘子的问题，子的问题，类推下去，一直到最后成为搬动一个，类推下去，一直到最后成为搬动一个盘子的问题。盘子的问题。这是一个典型的递归问题，递归结束于只搬动一个盘子。这是一个典型的递归问题，递归结束于只搬动一个盘子。函数的递归调用函数的递归调用算
7、法可以描述为：算法可以描述为：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；另一；另
8、一个命名为个命名为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,target);elsehanoi(n-1,source,target,temp);/将将n-1个盘子搬到中间柱个盘子搬到中间柱 move(source,target)
9、;/将最后一个盘子搬到目标柱将最后一个盘子搬到目标柱hanoi(n-1,temp,source,target);/将将n-1个盘子搬到目标柱个盘子搬到目标柱 void main()int n;cout输入盘子数：输入盘子数：n;hanoi(n,A,B,C);任务：用辗转相除法求最大公约数 任务：输入一个整数，用递归算法将整数倒序输出。N皇后问题 N皇后问题在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法。八皇后的两组解 分析：由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置都要进行试探和纠正(“回溯
10、”思想）。在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列放置的皇后；/纠正 一维数组实现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 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;
