學習要求： 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