什么是遞歸

　　百度百科：程序調用自身的編程技巧稱為遞歸（recursion）。

　　遞歸問題分析的核心

　　一個合法的遞歸定義包含兩個部分：基礎情況和遞歸部分。

　　分析一個遞歸問題就是列出遞歸定義表達式的過程。

　　上面那個電影院排數的問題表達式可以列為：

　　幾個經典題目

　　斐波那契數列

　　斐波那契數列的排列是：0，1，1，2，3，5，8，13，21，34，55，89，144……依次類推下去，你會發現，它后一個數等于前面兩個數的和。在這個數列中的數字，就被稱為斐波那契數。

　　遞歸思想：一個數等于前兩個數的和。(這并不是廢話，這是執行思路)

　　首先分析數列的遞歸表達式：

　　代碼如下:

　　可以看到，遞歸寫法簡單優美，省去考慮很多邊界條件的時間。當然，遞歸算法會保存很多的臨時數據，類似于堆棧的過程，如果棧深太深，就會造成內存用盡，程序崩潰的現象。Java為每個線程分配了棧大小，如果棧大小溢出，就會報錯，這時候還是選擇遞推好一點。

　　觀察下面的執行過程也會發現，本程序并沒有保存每次的運算結果，第三行的F(7)就執行了兩次，下層的F(1),F(2)的次數更是指數級增長。這也是本程序的一個弊端。

　　斐波那契執行過程：

　　階乘

　　遞歸思想：n!=n*(n-1)!(直接看公式吧)

　　首先分析數列的遞歸表達式：

　　代碼如下:

　　執行過程如下：

　　倒序輸出一個正整數

　　例如給出正整數n=12345，希望以各位數的逆序形式輸出，即輸出54321。

　　遞歸思想：首先輸出這個數的個位數，然后再輸出前面數字的個位數，直到之前沒數字。

　　首先分析數列的遞歸表達式：

　　代碼如下:

　　漢諾塔

　　超經典了的遞歸解決問題了：

　　法國數學家愛德華·盧卡斯曾編寫過一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。

　　數學描述就是：

　　有三根桿子X，Y，Z。X桿上有N個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至Y桿：

　　1.每次只能移動一個圓盤；

　　2.大盤不能疊在小盤上面。

　　遞歸思想：

　　1.將X桿上的n-1個圓盤都移到空閑的Z桿上，并且滿足上面的所有條件

　　2.將X桿上的第n個圓盤移到Y上

　　3.剩下問題就是將Z桿上的n-1個圓盤移動到Y上了

　　公式描述有點麻煩，用語言描述下吧：

　　1.以Y桿為中介，將前n-1個圓盤從X桿挪到Z桿上(本身就是一個n-1的漢諾塔問題了！)

　　2.將第n個圓盤移動到Y桿上

　　3.以X桿為中介，將Z桿上的n-1個圓盤移到Y桿上(本身就是一個n-1的漢諾塔問題了！)

　　代碼如下：

　　執行過程：

　　如果一秒鐘移動一次，世界毀滅需要多長時間呢？5845.54億年以上，而地球存在至今不過45億年，地球現在還是很安全的。

　　排列問題

　　輸入一個字符串，打印出該字符串中字符的所有排列。例如輸入字符串abc，則輸出由字符a、b、c所能排列出來的所有字符串abc、acb、bac、bca、cab和cba。

　　遞歸思想：

　　假如針對abc的排列，可以分成(1)以a開頭，加上bc的排列(2)以b開頭，加上ac的排列(3)以c開頭，加上ab的排列

　　本題用遞歸算法很巧妙，省去了用普通方法時保存數據狀態的繁瑣操作！