對(duì)于很多人來說，都知道遞歸，也能看的懂遞歸，但在實(shí)際項(xiàng)目過程中，卻不知道如何使用遞歸，這里給遞歸做個(gè)總結(jié)。
遞歸的定義
在數(shù)學(xué)與計(jì)算機(jī)科學(xué)中，遞歸(Recursion)是指在函數(shù)的定義中使用函數(shù)自身的方法。實(shí)際上，遞歸，顧名思義，其包含了兩個(gè)意思：遞和歸，這正是遞歸思想的精華所在。
通俗點(diǎn)講，我們可以把” 遞歸 “比喻成 “查字典 “，當(dāng)你查一個(gè)詞，發(fā)現(xiàn)這個(gè)詞的解釋中某個(gè)詞仍然不懂，于是你開始查這第二個(gè)詞。
可惜，第二個(gè)詞里仍然有不懂的詞，于是查第三個(gè)詞，這樣查下去，直到有一個(gè)詞的解釋是你完全能看懂的，那么遞歸走到了盡頭，然后你開始后退，逐個(gè)明白之前查過的每一個(gè)詞，最終，你明白了最開始那個(gè)詞的意思。
遞歸的思想
遞歸就是有去（遞去）有回（歸來），如下圖所示。“有去”是指：遞歸問題必須可以分解為若干個(gè)規(guī)模較小，與原問題形式相同的子問題，這些子問題可以用相同的解題思路來解決，就像上面例子中的鑰匙可以打開后面所有門上的鎖一樣；“有回”是指 : 這些問題的演化過程是一個(gè)從大到小，由近及遠(yuǎn)的過程，并且會(huì)有一個(gè)明確的終點(diǎn)(臨界點(diǎn))，一旦到達(dá)了這個(gè)臨界點(diǎn)，就不用再往更小、更遠(yuǎn)的地方走下去。最后，從這個(gè)臨界點(diǎn)開始，原路返回到原點(diǎn)，原問題解決。
遞歸的三大要素
- 明確遞歸終止條件;
- 給出遞歸終止時(shí)的處理辦法;
- 提取重復(fù)的邏輯，縮小問題規(guī)模;
明確遞歸終止條件
我們知道，遞歸就是有去有回，既然這樣，那么必然應(yīng)該有一個(gè)明確的臨界點(diǎn)，程序一旦到達(dá)了這個(gè)臨界點(diǎn)，就不用繼續(xù)往下遞去而是開始實(shí)實(shí)在在的歸來。換句話說，該臨界點(diǎn)就是一種簡(jiǎn)單情境，可以防止無限遞歸。
給出遞歸終止時(shí)的處理辦法
我們剛剛說到，在遞歸的臨界點(diǎn)存在一種簡(jiǎn)單情境，在這種簡(jiǎn)單情境下，我們應(yīng)該直接給出問題的解決方案。一般地，在這種情境下，問題的解決方案是直觀的、容易的。
提取重復(fù)的邏輯，縮小問題規(guī)模
我們?cè)陉U述遞歸思想內(nèi)涵時(shí)談到，遞歸問題必須可以分解為若干個(gè)規(guī)模較小、與原問題形式相同的子問題，這些子問題可以用相同的解題思路來解決。從程序?qū)崿F(xiàn)的角度而言，我們需要抽象出一個(gè)干凈利落的重復(fù)的邏輯，以便使用相同的方式解決子問題。
常見遞歸算法
下面總結(jié)一下常見的遞歸問題和實(shí)現(xiàn)算法。
斐波那契數(shù)列
斐波那契數(shù)列的排列是：0，1，1，2，3，5，8，13，21，34，55，89，144……依次類推下去，你會(huì)發(fā)現(xiàn)，它后一個(gè)數(shù)等于前面兩個(gè)數(shù)的和。在這個(gè)數(shù)列中的數(shù)字，就被稱為斐波那契數(shù)。
遞歸思想：一個(gè)數(shù)等于前兩個(gè)數(shù)的和。
首先分析數(shù)列的遞歸表達(dá)式：
代碼如下:
/**
* 斐波那契數(shù)列的遞歸寫法
* @param n
* @return
*/
long F(int n){
if (n<=1) return n;
return F(n-1)+F(n-2);
}
可以看到，遞歸寫法簡(jiǎn)單優(yōu)美，省去考慮很多邊界條件的時(shí)間。當(dāng)然，遞歸算法會(huì)保存很多的臨時(shí)數(shù)據(jù)，類似于堆棧的過程，如果棧深太深，就會(huì)造成內(nèi)存用盡，程序崩潰的現(xiàn)象。
階乘
遞歸思想：n! = n * (n-1)!
首先分析數(shù)列的遞歸表達(dá)式：
代碼如下:
long factorial(int n){
if (n <=1) return 1;
return j(n-1)*n;
}
倒序輸出一個(gè)正整數(shù)
例如給出正整數(shù) n=12345，希望以各位數(shù)的逆序形式輸出，即輸出54321。
遞歸思想：首先輸出這個(gè)數(shù)的個(gè)位數(shù)，然后再輸出前面數(shù)字的個(gè)位數(shù)，直到之前沒數(shù)字。
首先分析數(shù)列的遞歸表達(dá)式：
代碼如下:
/**
* 倒序輸出正整數(shù)的各位數(shù)
* @param n
*/
void printDigit(int n){
System.out.print(n%10);
if (n > 10){
printDigit(n/10);
}
}
漢諾塔
數(shù)學(xué)描述就是：
有三根桿子X，Y，Z。X桿上有N個(gè)(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規(guī)則將所有圓盤移至Y桿：
- 每次只能移動(dòng)一個(gè)圓盤；
- 大盤不能疊在小盤上面。
遞歸思想：
- 將X桿上的n-1個(gè)圓盤都移到空閑的Z桿上，并且滿足上面的所有條件
- 將X桿上的第n個(gè)圓盤移到Y(jié)上
- 剩下問題就是將Z桿上的n-1個(gè)圓盤移動(dòng)到Y(jié)上了
公式描述有點(diǎn)麻煩，用語言描述下吧：
- 以Y桿為中介，將前n-1個(gè)圓盤從X桿挪到Z桿上(本身就是一個(gè)n-1的漢諾塔問題了！)
- 將第n個(gè)圓盤移動(dòng)到Y(jié)桿上
- 以X桿為中介，將Z桿上的n-1個(gè)圓盤移到Y(jié)桿上(本身就是一個(gè)n-1的漢諾塔問題了！)
代碼如下：
/**
* 漢諾塔
* 有柱子 x z y，最終將x上的n個(gè)圓盤借助z移動(dòng)到y(tǒng)上
* 遞歸思想：
* 1.將x上的n-1個(gè)放入到z上，借助y
* 2.將x上的n圓盤放到y(tǒng)上
* 3.將z上的n-1個(gè)圓盤放入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);
}
}
遞歸的效率
還是拿斐波那契數(shù)列來做例子：
long Fib(int n){
if (n<=1) return n;
return Fib(n-1)+Fib(n-2);
}
這段代碼應(yīng)該算是短小精悍（執(zhí)行代碼只有一行），直觀清晰，而且非常符合許多程序員的代碼美學(xué)，是如果用這段代碼試試計(jì)算Fib(1000)我想就再也爽不起來了，它的運(yùn)行時(shí)間也許會(huì)讓你抓狂。
看來好看的代碼未必中用，如果程序在效率不能接受那美觀神馬的就都是浮云了。如果簡(jiǎn)單分析一下程序的執(zhí)行流，就會(huì)發(fā)現(xiàn)問題在哪，以計(jì)算Fibonacci(5)為例：
從上圖可以看出，在計(jì)算Fib(5)的過程中，F(xiàn)ib(1)計(jì)算了兩次、Fib(2)計(jì)算了3次，F(xiàn)ib(3)計(jì)算了兩次，本來只需要5次計(jì)算就可以完成的任務(wù)卻計(jì)算了9次。這個(gè)問題隨著規(guī)模的增加會(huì)愈發(fā)凸顯，以至于Fib(1000)已經(jīng)無法再可接受的時(shí)間內(nèi)算出。
我們當(dāng)時(shí)使用的是簡(jiǎn)單的用定義來求 fib(n)，也就是使用公式 fib(n) = fib(n-1) + fib(n-2)。這樣的想法是很容易想到的，可是仔細(xì)分析一下我們發(fā)現(xiàn)，當(dāng)調(diào)用fib(n-1)的時(shí)候，還要調(diào)用fib(n-2)，也就是說fib(n-2)調(diào)用了兩次，同樣的道理，調(diào)用f(n-2)時(shí)f(n-3)也調(diào)用了兩次，而這些冗余的調(diào)用是完全沒有必要的?？梢杂?jì)算這個(gè)算法的復(fù)雜度是指數(shù)級(jí)的。
由以上分析我們可以看到，遞歸在處理問題時(shí)要反復(fù)調(diào)用函數(shù)，這增大了它的空間和時(shí)間開銷，所以在使用迭代可以很容易解決的問題中，使用遞歸雖然可以簡(jiǎn)化思維過程，但效率上并不合算。效率和開銷問題是遞歸最大的缺點(diǎn)。
雖然有這樣的缺點(diǎn)，但是遞歸的力量仍然是巨大而不可忽視的，因?yàn)橛行﹩栴}使用迭代算法是很難甚至無法解決的。這時(shí)遞歸的作用就顯示出來了。
