遞歸算法

1. 前言

本節(jié)內(nèi)容是遞歸算法系列之一：遞歸的介紹，主要介紹了遞歸的定義，選擇了數(shù)學(xué)歸納法這一數(shù)學(xué)模型幫助大家可以更好的理解遞歸的概念，然后明確了一個遞歸算法必須要具備的三要素，最后說明了一下哪些問題適合應(yīng)用遞歸算法求解分析。

2. 什么是遞歸？

遞歸（Recursion），是計算機科學(xué)與技術(shù)領(lǐng)域中一種常見的算法思想。

在數(shù)學(xué)和計算機領(lǐng)域中，遞歸主要是指在函數(shù)的定義中使用函數(shù)自身的方法。顧名思義，遞歸主要包含兩個意思，遞和歸，這個是遞歸思想的精華所在。遞歸就是有去（遞去）有回（歸來）。“有去” 是指遞歸問題可以分解成若干個規(guī)模較小、與原問題形式相同的子問題，這些子問題可以和原問題用相同的方法來求解?！坝谢亍?是指這些問題的演化過程是一個從大到小，并且最終會有一個明確的終點，一旦達到終點，就可以從終點原路返回，解決原問題。

更為直接的說法就是：遞歸的基本思想就是把大問題轉(zhuǎn)化為相似的小問題解決。特別是在程序中的函數(shù)實現(xiàn)時，大問題的解決方案和小問題是一模一樣的，所以就產(chǎn)生解決一個問題會調(diào)用函數(shù)本身的情況，這個也是遞歸的定義。

3. 用數(shù)學(xué)歸納法理解遞歸思想

很多時候，大家都在思考遞歸在數(shù)學(xué)上面應(yīng)該如何表示了，畢竟對于數(shù)學(xué)的簡單理解比起我們直接寫代碼起來還是要簡單很多的。觀察遞歸，我們會很容易發(fā)現(xiàn)遞歸的數(shù)學(xué)模型類似于數(shù)學(xué)歸納法，這個在高中的數(shù)列里面就已經(jīng)開始應(yīng)用了。數(shù)學(xué)歸納法常見的描述如下

最簡單和常見的數(shù)學(xué)歸納法是證明當(dāng) n 等于任意一個自然數(shù)時某命題成立。證明分下面兩步：

1. 證明當(dāng) n= 1 時命題成立。
2. 假設(shè) n=m 時命題成立，那么可以 推導(dǎo)出在 n=m+1 時命題也成立。（m 代表任意自然數(shù)）

數(shù)學(xué)歸納法適用于將需要解決的原問題轉(zhuǎn)換為解決他的子問題，而其中的子問題又可以變成子問題的子問題，而且這些問題都是同一個模型，可以用相同的處理邏輯歸納處理。當(dāng)然有一個是例外的，就是歸納結(jié)束的那一個處理方法不能適用于其他的歸納處理項。遞歸同樣的是將大的問題分解成小問題處理，然后會有一個遞歸的終止條件，滿足終止條件之后開始回歸。

數(shù)學(xué)里面有一個很有名的斐波那契數(shù)列，我們在編程求解斐波那契數(shù)列的時候就會用到遞歸的思想，在后續(xù)的內(nèi)部中會具體講到。

4. 遞歸的三要素

在明確遞歸的定義及數(shù)學(xué)模型之后，我們需要掌握遞歸的三要素：

1. 遞歸終止條件；
2. 遞歸終止時候的處理方法；
3. 遞歸中重復(fù)的邏輯提取，縮小問題規(guī)模。

4.1 遞歸終止條件

按照之前的說明，遞歸應(yīng)該是有去有回的，這樣遞歸就必須有一個明確的分界點，遞歸可以在什么時候結(jié)束。程序一旦達到這個臨界點，就不用繼續(xù)遞歸重復(fù)下去了。簡單來說，遞歸的終止條件就是為了防止出現(xiàn)無限遞歸的情況。

4.2 遞歸終止時的處理方法

如前面說到遞歸需要一個終止條件一樣，在達到遞歸的終止條件時，需要有一個對應(yīng)終止條件的程序處理方法。一般而言，在達到遞歸的終止條件時，對應(yīng)的問題都是很容易解決的，可以快速的給出問題的解決方案。

4.3 遞歸中重復(fù)的邏輯提取，縮小問題規(guī)模

遞歸的本質(zhì)上還是要將一個大的問題分解成各個邏輯相同的小問題，所以遞歸過程中一個重要的步驟就是提取遞歸中重復(fù)的邏輯規(guī)則，以便利用相同的處理方式進行處理。

按照以上遞歸的三要素，遞歸程序的一般處理可以總結(jié)成下面的偽代碼：

recursion(big_problem){
   if (end_condition){  //滿足遞歸的終止條件
       solve_end_condition;  //處理終止條件下的邏輯
       end;  //遞歸結(jié)束
   }else {
       recursion(small_problem);  //遞歸中重復(fù)的邏輯提取，縮小問題規(guī)模
   }
}

5. 遞歸的應(yīng)用場景

在日常的生活學(xué)習(xí)中，遞歸算法一般可以用來解決很多實際問題?；仡櫼幌挛覀冎皩W(xué)習(xí)的排序算法，其中快速排序利用了遞歸的思想進行解決?？偠灾?，遞歸在很多場景中都有應(yīng)用。

比如說一個常見的對于操作系統(tǒng)里面刪除指定路徑下的文件夾里內(nèi)容以及子文件夾里面內(nèi)容的操作，就可以利用遞歸思想完成。這個時候遞歸的終止條件就是判斷當(dāng)前路徑是文件，就可以直接刪除；發(fā)現(xiàn)當(dāng)前路徑是文件夾，則遞歸調(diào)用方法，進入文件夾內(nèi)部刪除里面的文件內(nèi)容。

總而言之，遞歸問題在現(xiàn)實學(xué)習(xí)科研中經(jīng)常會遇到，這是一種解決問題的思路與方法，將大問題拆分成小問題，然后求解小問題之后回歸歸納，得出整個問題的求解結(jié)果。

6. 小結(jié)

本節(jié)主要介紹了遞歸的定義及基本概念，在學(xué)完本節(jié)課程之后，需要明白遞歸的基礎(chǔ)邏輯是什么樣的，如何自己去設(shè)計一個遞歸算法，在設(shè)計一個遞歸算法時需要考慮到哪些問題，以及我們?nèi)粘Ｖ谐Ｒ姷倪f歸問題。