算法之美：解讀遞歸算法原理和效率

對于很多人來說，都知道遞歸，也能看的懂遞歸，但在實際項目過程中，卻不知道如何使用遞歸，這里給遞歸做個總結。

遞歸的定義

在數學與計算機科學中，遞歸(Recursion)是指在函數的定義中使用函數自身的方法。實際上，遞歸，顧名思義，其包含了兩個意思：遞和歸，這正是遞歸思想的精華所在。

通俗點講，我們可以把” 遞歸 “比喻成 “查字典 “，當你查一個詞，發現這個詞的解釋中某個詞仍然不懂，于是你開始查這第二個詞。

可惜，第二個詞里仍然有不懂的詞，于是查第三個詞，這樣查下去，直到有一個詞的解釋是你完全能看懂的，那么遞歸走到了盡頭，然后你開始后退，逐個明白之前查過的每一個詞，最終，你明白了最開始那個詞的意思。

遞歸的思想

遞歸就是有去（遞去）有回（歸來），如下圖所示。“有去”是指：遞歸問題必須可以分解為若干個規模較小，與原問題形式相同的子問題，這些子問題可以用相同的解題思路來解決，就像上面例子中的鑰匙可以打開后面所有門上的鎖一樣；“有回”是指 : 這些問題的演化過程是一個從大到小，由近及遠的過程，并且會有一個明確的終點(臨界點)，一旦到達了這個臨界點，就不用再往更小、更遠的地方走下去。最后，從這個臨界點開始，原路返回到原點，原問題解決。

遞歸的三大要素

明確遞歸終止條件;
給出遞歸終止時的處理辦法;
提取重復的邏輯，縮小問題規模;

明確遞歸終止條件

我們知道，遞歸就是有去有回，既然這樣，那么必然應該有一個明確的臨界點，程序一旦到達了這個臨界點，就不用繼續往下遞去而是開始實實在在的歸來。換句話說，該臨界點就是一種簡單情境，可以防止無限遞歸。

給出遞歸終止時的處理辦法

我們剛剛說到，在遞歸的臨界點存在一種簡單情境，在這種簡單情境下，我們應該直接給出問題的解決方案。一般地，在這種情境下，問題的解決方案是直觀的、容易的。

提取重復的邏輯，縮小問題規模

我們在闡述遞歸思想內涵時談到，遞歸問題必須可以分解為若干個規模較小、與原問題形式相同的子問題，這些子問題可以用相同的解題思路來解決。從程序實現的角度而言，我們需要抽象出一個干凈利落的重復的邏輯，以便使用相同的方式解決子問題。

常見遞歸算法

下面總結一下常見的遞歸問題和實現算法。

斐波那契數列

斐波那契數列的排列是：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);
}

可以看到，遞歸寫法簡單優美，省去考慮很多邊界條件的時間。當然，遞歸算法會保存很多的臨時數據，類似于堆棧的過程，如果棧深太深，就會造成內存用盡，程序崩潰的現象。

階乘

遞歸思想：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);
 }
}

漢諾塔

數學描述就是：

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

每次只能移動一個圓盤；
大盤不能疊在小盤上面。

遞歸思想：

將X桿上的n-1個圓盤都移到空閑的Z桿上，并且滿足上面的所有條件
將X桿上的第n個圓盤移到Y上
剩下問題就是將Z桿上的n-1個圓盤移動到Y上了

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

以Y桿為中介，將前n-1個圓盤從X桿挪到Z桿上(本身就是一個n-1的漢諾塔問題了！)
將第n個圓盤移動到Y桿上
以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);
 }
}

遞歸的效率

還是拿斐波那契數列來做例子：

long Fib(int n){
 if (n<=1) return n;
 return Fib(n-1)+Fib(n-2);
}

這段代碼應該算是短小精悍（執行代碼只有一行），直觀清晰，而且非常符合許多程序員的代碼美學，是如果用這段代碼試試計算Fib(1000)我想就再也爽不起來了，它的運行時間也許會讓你抓狂。

看來好看的代碼未必中用，如果程序在效率不能接受那美觀神馬的就都是浮云了。如果簡單分析一下程序的執行流，就會發現問題在哪，以計算Fibonacci(5)為例：

從上圖可以看出，在計算Fib(5)的過程中，Fib(1)計算了兩次、Fib(2)計算了3次，Fib(3)計算了兩次，本來只需要5次計算就可以完成的任務卻計算了9次。這個問題隨著規模的增加會愈發凸顯，以至于Fib(1000)已經無法再可接受的時間內算出。

我們當時使用的是簡單的用定義來求 fib(n)，也就是使用公式 fib(n) = fib(n-1) + fib(n-2)。這樣的想法是很容易想到的，可是仔細分析一下我們發現，當調用fib(n-1)的時候，還要調用fib(n-2)，也就是說fib(n-2)調用了兩次，同樣的道理，調用f(n-2)時f(n-3)也調用了兩次，而這些冗余的調用是完全沒有必要的。可以計算這個算法的復雜度是指數級的。

由以上分析我們可以看到，遞歸在處理問題時要反復調用函數，這增大了它的空間和時間開銷，所以在使用迭代可以很容易解決的問題中，使用遞歸雖然可以簡化思維過程，但效率上并不合算。效率和開銷問題是遞歸最大的缺點。

雖然有這樣的缺點，但是遞歸的力量仍然是巨大而不可忽視的，因為有些問題使用迭代算法是很難甚至無法解決的。這時遞歸的作用就顯示出來了。