1.遞歸的基本思想
（1）何為遞歸？
遞歸顧名思義就是′遞′和′歸′

👀所謂的‘遞’也就是“向下遞去”，這個(gè)問題可以分解為若干個(gè)且形式相同的子問題，這些子問題可以使用相同的思路來解決。
👀所謂的‘歸’也就是“歸來的意思”，什么時(shí)候歸來？所以涉及到了臨界點(diǎn)，也就是‘遞’中的分解終止條件。

（2）遞歸的工作原理？

💦根據(jù)以上分析可以發(fā)現(xiàn)這個(gè)流程和棧的工作原理一致，遞歸調(diào)用就是通過棧這種數(shù)據(jù)結(jié)構(gòu)完成的。整個(gè)過程實(shí)際上就是一個(gè)棧的入棧和出棧問題。然而我們并不需要關(guān)心這個(gè)棧的實(shí)現(xiàn)，這個(gè)過程是由系統(tǒng)來完成的。

（3）遞歸的慣性解題思路
遞歸本質(zhì)上類似數(shù)學(xué)中的歸納法，但又有所不同。（遞歸是從F(n)倒推到F(1),然后在F(1)回溯到F(n)；相比于歸納法多了一步。）

void func(mode) {if (endCondition) //臨界條件{constExpression //處理方法} else {accumrateExpreesion //歸納項(xiàng)mode = expression //步進(jìn)表達(dá)式func(mode) //調(diào)用本身，遞歸} }

（4）遞歸的三要素

💥1、縮小問題規(guī)模

👀這個(gè)縮小問題規(guī)模可以根據(jù)歸納法先進(jìn)行回推，比如讓求S(n),我們可以先求當(dāng)n=1的解決方法，再求n=2時(shí)的解決方法…一直歸納到S(n)；這樣我們就可以推導(dǎo)出關(guān)系式S(n)=S(n-1)+?

💥2、明確遞歸終止條件

👀遞歸既然有去有回，就必須有一個(gè)臨界條件，當(dāng)程序到達(dá)這個(gè)臨界值就必須進(jìn)行歸來；否者就肯定會造成無線遞歸下去！

💥3、給出遞歸終止時(shí)的處理辦法

👀根據(jù)上文中闡述的遞歸的工作原理，遞歸是通過棧來實(shí)現(xiàn)的；當(dāng)程序到達(dá)臨界條件時(shí)，后續(xù)必須進(jìn)行出棧。了解函數(shù)的壓棧和出棧過程，函數(shù)出棧也就是返回到上一個(gè)函數(shù)的調(diào)用處繼續(xù)執(zhí)行。例如求解F(n)，遞推式是F(n)=F(n-1)+F(n-2)，終止條件F(1)=1，F(0)=0；它的流程是每次進(jìn)行壓棧F(n-1)、F(n-2)，當(dāng)達(dá)到終止條件時(shí)進(jìn)行函數(shù)的出棧，那么返回什么值呢？根據(jù)遞歸的倒數(shù)第一步F(2)=F(1)+F(0)所以返回的是F(1)+F(0),也就是1.

2.分治法的基本思想

對于一個(gè)規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較小）則直接解決，否則將其分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設(shè)計(jì)策略叫做分治法。【簡單了說就是“分而治之”】

3.分治法所能解決的問題一般具有以下幾個(gè)特征：
（1）該問題的規(guī)模縮小到一定的程度就可以容易地解決
（2）該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
（3）利用該問題分解出的子問題的解可以合并為該問題的解；
（4）該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題

4.解決該問題的步驟
問題：給定N個(gè)數(shù)據(jù)和待查找的數(shù)據(jù)x，采用二分查找算法來搜索x，輸出x在N個(gè)數(shù)據(jù)中的位置
（1）解題思路
取數(shù)組中間索引mid=(begin+end)/2，比較待搜索值與中間值，如果待搜索值>中間值，則去中間索引的右邊繼續(xù)搜索，反之去左邊；就這樣循環(huán)下去，直到搜索到該值或者begin<end時(shí)終止程序。
（2）分析以上算法思想的弊端
根據(jù)它的 int mid = (begin+end)/2 ，我們可以推算二分算法適用于什么場景；
假設(shè)一個(gè)數(shù)組為arr[1,2,3,4,5…,98,99,100] ，我們要找尋1這個(gè)值，那么需要幾次找到呢？看下面的運(yùn)行結(jié)果

可以看出經(jīng)歷了六次循環(huán)調(diào)用才找到；如果找value=50,那么一次就能成功！所以這個(gè)調(diào)用多少次與mid的取值也有很大關(guān)系；

5.對二分查找算法進(jìn)行優(yōu)化
分析mid=(begin+end)/2，看出begin、end無法做出改變，那么只有對1/2進(jìn)行改動；mid=begin + (begin+end) / {(value-arr[begin])/(arr[end]-arr[begin])}，根據(jù)上文中找尋1，我們可以算出mid = 1。
根據(jù)上文進(jìn)行分析，這個(gè)插值查找算法是對二分查找算法的改進(jìn)。mid=begin + (begin+end) / {(value-arr[begin]) / (arr[end]-arr[begin])}，這也就是插值查找算法。

• 優(yōu)化思路如下：
• 上述二分思想f = 1 / 2 （f為變化率)
• 將mid隨著x值的大小做不斷變化 f = (x - arr[begin]) / (arr[end] - arr[begin])
• 則 mid=f * (begin+end)

6.代碼與結(jié)果展示
（1）非遞歸方式

/*** @param arr 待搜索數(shù)組* @param begin 頭索引* @param end 尾索引* @param x 待搜索值* @return 對應(yīng)的下標(biāo)* 缺點(diǎn)：對于某種極端的情況需要一直進(jìn)行搜索（比如1~100這種均衡的情況，如果剛好搜索1這個(gè)數(shù)，就需要搜索6次【50->25->12->6->3->1】*/public static int binarySearch(int[] arr, int begin, int end, int x) {int mid = (begin + end) / 2;while (begin <= end) {if (arr[mid] > x) {end = mid - 1;} else if (arr[mid] < x) {begin = mid + 1;} else if (arr[mid] == x){return mid;}mid = (begin + end) / 2;}return -1;} （2）插值優(yōu)化/*** @param arr 待搜索數(shù)組* @param begin 頭索引* @param end 尾索引* @param x 待搜索值* @return 對應(yīng)的下標(biāo)* 上述方法對于【1~100】這種均衡的極端情況不適用，所以需要進(jìn)行優(yōu)化處理* 說到底是中間值的取法問題（好的中間值取法能夠快速定位的搜索值），所以該二分查找優(yōu)化的本質(zhì)上是對中間值取法的優(yōu)化* 優(yōu)化思路如下：* 上述方法f = 1 / 2 （f為變化率)* 將mid隨著x值的大小做不斷變化 f = (x - arr[begin]) / (arr[end] - arr[begin])* 則 mid=begin + f * (begin+end)*/public static int binarySearch2(int[] arr, int begin, int end, int x) {int mid = (begin + end) * (x - arr[begin]) / (arr[end] - arr[begin]);while (begin <= end && x > arr[begin] && x < arr[end]) {if (arr[mid] > x) {end = mid - 1;} else if (arr[mid] < x) {begin = mid + 1;} else if (arr[mid] == x) {return mid;}mid = begin + (begin + end) * (x - arr[begin]) / (arr[end] - arr[begin]);}return -1;} （3）遞歸方式/*** mid = (begin + end) / 2* @param arr 待搜索數(shù)組* @param begin 頭索引* @param end 尾索引* @param x 待搜索值* @return 對應(yīng)的下標(biāo)*/public static int binarySearch3(int[] arr, int begin, int end, int x) {if (begin > end) {return -1;}int mid = (begin + end) / 2;if (arr[mid] > x) {return binarySearch3(arr, begin, mid - 1, x);} else if (arr[mid] < x) {return binarySearch3(arr, mid + 1, end, x);} else {return mid;} }

（4）插值優(yōu)化

/*** int mid = begin + (begin + end) * [(x - arr[begin]) / (arr[end] - arr[begin])];* @param arr 待搜索數(shù)組* @param begin 頭索引* @param end 尾索引* @param x 待搜索值* @return 對應(yīng)的下標(biāo)*/public static int binarySearch4(int[] arr, int begin, int end, int x) {if (begin > end || x < arr[begin] || x > arr[end]) {return -1;}int mid = begin + (begin + end) * (x - arr[begin]) / (arr[end] - arr[begin]);if (arr[mid] > x) {return binarySearch4(arr, begin, mid - 1, x);} else if (arr[mid] < x) {return binarySearch4(arr, mid + 1, end, x);} else {return mid;} }

7.測試結(jié)果

待搜索數(shù)組：int[] arr = {1, 3, 4, 5, 8, 11, 23, 77};

當(dāng)搜索x = 3時(shí)，結(jié)果如下

當(dāng)搜索x = -11時(shí)，結(jié)果如下

當(dāng)搜索x = 156時(shí)，結(jié)果如下

當(dāng)搜索x =77時(shí)，結(jié)果如下

總結(jié)

以上是生活随笔為你收集整理的实验2 递归和分治法（二分查找）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。