学习要求： 1.掌握递归的编程技巧
2.掌握递归与迭代的转换
3.理解递归的优缺点
学习内容：
1.实现汉诺伊塔的递归算法，并以此为例理解递归程序运行的细节（可用单步调试分析递归）。
2.编程实现阶乘，斐波那契数列的递归的程序和迭代的程序，分析递归和迭代算法空间和算法时间上的区别。
3.实现和分析全排列产生器的递归程序，掌握这种形式的递归。
所谓的全排列产生器是指：给定n(n>=1)个元素的集合，要求输出该集合的所有可能的排列。列如，如果该集合为{a，b，c}，那么排列的集合为{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)}.
可以很容易看出，给定n个元素，有n！个不同的排列。通过察看具有四个元素的集合(a,b,c,d)，可以得到一个简单的算法，答案通过下面的方式得到：
1.a加上(b,c,d)的所有排列
2.b加上(a,c,d)的所有排列
3.c加上(a,b,d)的所有排列
4.d加上(a,b,c)的所有排列
“加上所有的排列”已具有递归的思想！意味着我们解决具有n-1个元素的问题，也可以用来解决n个元素的问题。下面的程序就是一个递归解决的全排列产生器(c++)：
//Type 排列集合中元素的类型，n为集合元素的个数
//k为当前选择的元素k
void perm(Type a[],int k,int n)
{
if(k==n)
{
for(int i=0;i<n;i++)
cout<<a[i]<<" "; //输出元素
cout<<endl;
}
else
for(int i=k;i<n;i++)
{
Type t=a[k];a[k]=a[i];a[i]=t;
perm(a,k+1,n);
t=a[k];a[k]=a[i];a[i]=t;
}
}
调用perm(a,0,n)就可以输出所有排列。
实现和分析该算法，并要理解算法中每一步的运行（可以单步调试观察），深刻理解递归的堆栈与出栈！
4.编写一个集合的幂集的递归程序。描述如下：如果S具有n个元素的集合，S的 幂集 为S所有可能子集的集合。列如，如果S=(a,b,c)，那么powerset(S)={(),(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c)}。编写一个计算powerset(S)的递归程序。
完成时间：一周
参考资料：全排列产生器算法--《计算机算法（C++版）》 机械工业出版
幂集的递归程序--http://www.cnblogs.com/yxin1322/archive/2008/03/08/1096685.html