什麼是遞歸

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

借用知乎上Memoria的回答：

假設你在一個電影院，你想知道自己坐在哪一排，但是前面人很多，你懶得去數了，於是你問前一排的人「你坐在哪一排？」，這樣前面的人 (代號 A) 回答你以後，你就知道自己在哪一排了——只要把 A 的答案加一，就是自己所在的排了。不料 A 比你還懶，他也不想數，於是他也問他前面的人 B「你坐在哪一排？」，這樣 A 可以用和你一模一樣的步驟知道自己所在的排。然後 B 也如法炮製。直到他們這一串人問到了最前面的一排，第一排的人告訴問問題的人「我在第一排」。最後大家就都知道自己在哪一排了。

遞歸問題分析的核心

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

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

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

幾個經典題目

斐波那契數列

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

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

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

代碼如下:

/**
 * 斐波那契數列的遞歸寫法
 * 核心：一個小的解決終點，然後大的問題可以循環在小問題上解決
 * @param n
 * @return
 */
long F(int n){
 if (n<=1) return n;
 return F(n-1)+F(n-2);
}
/**
 * 斐波那契數列的遞推寫法
 * @param n
 * @return
 */
long F1(int n){
 if (n<=1) return n;
 long fn = 0;
 long fn_1 = 1;
 long fn_2 = 0;
 for (int i = 2; i <= n; i++) {
 fn = fn_1 + fn_2;
 fn_2 = fn_1;
 fn_1 = fn;
 }
 return fn;
}

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

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

斐波那契執行過程：

階乘

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

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

代碼如下:

long factorial(int n){
 if (n <=1) return 1;
 return j(n-1)*n;
}

執行過程如下：

倒序輸出一個正整數

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

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

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

代碼如下:

/**
 * 倒序輸出正整數的各位數
 * @param n
 */
void printDigit(int n){
 System.out.print(n%10);
 if (n > 10){
 printDigit(n/10);
 }
}

漢諾塔

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

法國數學家愛德華·盧卡斯曾編寫過一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的聖廟裡，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的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的漢諾塔問題了！)

代碼如下：

/**
 * 漢諾塔
 * 有柱子 x z y，最終將x上的n個圓盤藉助z移動到y上
 * 遞歸思想：
 * 1.將x上的n-1個放入到z上，藉助y
 * 2.將x上的n圓盤放到y上
 * 3.將z上的n-1個圓盤放入y
 * @param n
 * @param from
 * @param tmp
 * @param to
 */
void hanoi(int n,char from,char tmp,char to){
 if (n>0) {
 hanoi(n - 1, from, to, tmp);
 System.out.println("take " + n + " from " + from + " to " + to);
 hanoi(n - 1, tmp, from, to);
 }
}

執行過程：

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

排列問題

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

遞歸思想：

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

/**
 * 產生排列組合的遞歸寫法
 * @param t 數組
 * @param k 起始排列值
 * @param n 數組長度
 */
void pai(int[] t, int k, int n){
 if (k == n-1){//輸出這個排列
 for (int i = 0; i < n; i++) {
 System.out.print(t[i] + " ");
 }
 System.out.println();
 }else {
 for (int i = k; i < n; i++) {
 int tmp = t[i]; t[i] = t[k]; t[k] = tmp;//一次挑選n個字母中的一個,和前位置替換
 pai(t, k+1, n); //再對其餘的n-1個字母一次挑選
 tmp = t[i]; t[i] = t[k]; t[k] = tmp; //再換回來
 }
 }
}

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

我這裡有一些Java面試題和答案：Memcached、Redis、Nginx、ActiveMQ、RabbitMQ、Kafka、JVM、Netty、併發編程、Spring、SpringMVC、MyBatis、Dubbo、Spring Boot、Spring Cloud。有需要的朋友，可以關注+轉發支持一波~，私信：“資料”免費領取。