摸魚心法第一章——和配置文件說拜拜
為了能摸魚我們團(tuán)隊做了容器化，但是帶來的問題是服務(wù)配置文件很麻煩，然后大家在群里進(jìn)行了“親切友好”的溝通圖片圖片圖片圖片對比就對比，簡單對比下獨(dú)立配置中心和k8s作為配
無論是刷算法題，還是日常開發(fā)，遞歸都是一個非常常用的解決問題的思路。利用遞歸思維，我們可以使用少量的代碼解決復(fù)雜的問題。不過在剛開始的時候，遞歸通常沒有那么容易理解，我們就從圖示中的幾個方向，系統(tǒng)的為大家介紹遞歸的學(xué)習(xí)與運(yùn)用。
遞歸是一種迭代思維。是對復(fù)雜問題的一種拆解。如果我們重復(fù)的可以將問題拆解為同類型的子問題，那么，這就是一個可以使用遞歸的場景。
例如，現(xiàn)在我給你一個需求，需要你計算從 1 ～ 100 的所有數(shù)的總和。此時，我們可以對這個需求進(jìn)行拆解。
首先我們加入已經(jīng)定義好了一個方法，用來計算最小值遞增到最大值的數(shù)字總和。
function accumulation(min, max) {}該方法目前只用于案例演示，語義上表示從 min 到 max 遞增數(shù)字的累加總和，無代碼實(shí)現(xiàn)，只有語義表達(dá)。
有了這個函數(shù)之后，我們可以把剛才的需求簡單表示為 accumulation(1, 100)。
但是 accumulation(1, 100) 是一個復(fù)雜問題，我們可以將其拆解為：
accumulation(1, 99) + 100拆解之后，我們需要解決的問題就稍微簡單了一些，變成了 accumulation(1, 99) + 100。x + 100 就很簡單，心算都能得出。但是 accumulation(1 + 99) 依然比較復(fù)雜，因此，我們可以重復(fù)剛才的思維，將拆解為。
accumulation(1, 98) + 99重復(fù)下去，我們會發(fā)現(xiàn)，一個大的問題，最終會被我們拆解為。
accumulation(1, 97) + 98accumulation(1, 96) + 97...accumulation(1, 2) + 3...accumulation(1 + 2) 很容易能得出答案。
我們這里使用的是一個非常基礎(chǔ)的例子來演示遞歸的思維，并非為了探討什么樣的計算方式來實(shí)現(xiàn)數(shù)字累加更合適。
在代碼實(shí)現(xiàn)中，遞歸主要包含兩個部分。
在上面的累加案例中，我們思考 accumulation(min, max) 的內(nèi)部實(shí)現(xiàn)。
首先邊界條件為：當(dāng) max 與 min 想等時，我們就沒必要繼續(xù)拆解下去了，此時，我們只需要返回 min 本身的值即可。
其他時候就調(diào)用自身，因此，最終代碼實(shí)現(xiàn)為。
function accumulation(min, max) { // 遞歸停止條件 if (max === min) { return min } // 拆解為同類子問題，并調(diào)用自身 return accumulation(min, max - 1) + max}該方法的 rust 實(shí)現(xiàn)為。
如果你沒有學(xué)習(xí)過 rust，可跳過該部分，不影響 js 的學(xué)習(xí)。
fn accumulation(min: i32, max: i32) -> i32 { if min == max { return min; } accumulation(min, max - 1) + max}這里需要特別注意的是，遞歸的邏輯，是先拆解，后邏輯運(yùn)算。在這個案例中，拆解的過程我們是從 accumulation(1, 100) 拆解到 accumulation(1, 1)，然后再回過頭來開始進(jìn)行運(yùn)算。
下面展示了該案例中，當(dāng)我們調(diào)用 accumulation(1, 100) 時的真實(shí)運(yùn)算過程。他與我們在思維上做拆解的過程是反過來的。
accumulation(1, 1) -> 1accumulation(1, 2) -> accumulation(1, 1) + 2 -> 3accumulation(1, 3) -> accumulation(1, 2) + 3 -> 6accumulation(1, 4) -> accumulation(1, 3) + 4 -> 10...accumulation(1, 97) -> accumulation(1, 96) + 97 -> 4753accumulation(1, 98) -> accumulation(1, 97) + 98 -> 4851accumulation(1, 99) -> accumulation(1, 98) + 99 -> 4950accumulation(1, 100) -> accumulation(1, 99) + 100 -> 5050因此，遞歸思維的強(qiáng)大之處就在于我們不需要花太多的精力把這個真實(shí)的運(yùn)算過程考慮得非常完善，計算機(jī)會幫我們做這個事情，而我們只需要知道如何拆解問題，就能最終把問題解決。
在數(shù)學(xué)上有一個常見的概念，叫做斐波那契數(shù)列。它指的是這樣一個數(shù)列：1、1、2、3、5、8、13、21、...
它的規(guī)律為：當(dāng)前數(shù)字，總等于它前面兩個數(shù)字之和。我們需要封裝一個函數(shù)，用來計算第 n 個數(shù)字的斐波那契值是多少。
function fibonacci(n) {}我們約定 n 是從 1 開始遞增的正整數(shù)。
首先思考邊界條件：當(dāng) n = 1 或者 n = 2 時，斐波那契值都是 1。
然后我們來拆解問題，例如我們要算 fibonacci(50)，按照規(guī)律，他就應(yīng)該等價于。
fibonacci(48) + fibonacci(49)此時我們會發(fā)現(xiàn)，斐波那契數(shù)列的遞歸運(yùn)算過程要比剛才數(shù)字累加的計算復(fù)雜，但是我們并不需要關(guān)注它到底最后是如何計算的，我們只需要確保邊界條件和拆解思路是正確的即可，因此，思考到這里就可以直接給出代碼實(shí)現(xiàn)。
許多人在初學(xué)時理解不了遞歸是因為他試圖在腦海中完整的呈現(xiàn)遞歸的壓棧過程，講道理，人腦能壓幾個棧啊 ～ ～
function fibonacci(n) { if (n == 1 || n == 2) { return 1 } return fibonacci(n - 2) + fibonacci(n - 1)}當(dāng)然這樣會在傳入數(shù)字很大的時候存在過多的計算，因此這個場景使用遞歸來解決并非最好的方案，本文采用該案例只用于學(xué)習(xí)使用。
// rust 實(shí)現(xiàn)fn fibonacci(n: i32) -> i32 { if n == 1 || n == 2 { return 1 } fibonacci(n - 2) + fibonacci(n - 1)}在上面我們對于斐波那契方案的解法中，雖然解決了問題，但是當(dāng)我傳入的 n 值變大時，會存在大量的冗余計算。
例如，當(dāng)我傳入 50，那么會遞歸的去算 fibonacci(48) 與 fibonacci(49)，但是，當(dāng)我們拆解 fibonacci(49) 時，又會再去算一次 fibonacci(48)。
這樣拆解下去，重復(fù)運(yùn)算的量非常大，因此我們需要想個辦法來解決這個問題。一個好的思路就是我們把算過的值找個地方存起來，下次遇到就直接從緩存中取值即可，而不用重復(fù)計算，因此我們把代碼改進(jìn)如下。
// 定義一個數(shù)組來緩存計算結(jié)果const cache = []function fibonacci(n) { if (n == 1 || n == 2) { return 1 } if (!cache[n]) { cache[n] = fibonacci(n - 2) + fibonacci(n - 1) } return cache[n]}這種實(shí)現(xiàn)方式是我們在全局變量中，定義了一個數(shù)組來緩存運(yùn)算結(jié)果，很顯然，這并不是理想的實(shí)現(xiàn)。
我們需要調(diào)整寫法，將緩存數(shù)組搞到 fibonacci 內(nèi)部中來。在 JavaScript 中，可以利用函數(shù)傳入引用數(shù)據(jù)類型的按引用傳遞特性，來達(dá)到引用數(shù)據(jù)的共享。
代碼實(shí)現(xiàn)如下：
// Implement it with jsfunction fibonacci(n, cache) { const __cache = cache || [] if (n == 1 || n == 2) { return 1 } if (!__cache[n]) { __cache[n] = fibonacci(n - 2, __cache) + fibonacci(n - 1, __cache) } return __cache[n]}// Implement it with ruststruct Fabonacci { cache: Vec<usize>}impl Fabonacci { fn new() -> Fabonacci { return Fabonacci { cache: vec![0, 1, 1] } } fn at(&mut self, n: usize) -> usize { return match self.cache.get(n) { Some(num) => *num, None => { let v = self.at(n - 1) + self.at(n - 2); self.cache.push(v); v } } }}let mut fabonacci = Fabonacci::new();print!("fabonacci: {}", fabonacci.at(10))我們再來回顧一下遞歸思維：重復(fù)的將問題拆分為同類型的子問題。完整來說，這是一個拆解 -> 直到觸發(fā)邊界終止條件 -> 運(yùn)算合并的過程。
我們可以用下圖來表達(dá)這個過程。
當(dāng)我們熟悉了這個基礎(chǔ)的遞歸思維之后，那么我們就可以對拆分方式于合并方式進(jìn)行進(jìn)一步的思考，以學(xué)習(xí)到更多的高級用法。
分治策略就是在遞歸的基礎(chǔ)之上，對拆分方式進(jìn)行調(diào)整演變出來的一種高效解題思路。我們以歸并排序為例來為大家講解分治策略。
歸并排序是一種對數(shù)組進(jìn)行快速排序的一種排序方式。
分：在拆分階段，我們通過遞歸從數(shù)組的中心位置進(jìn)行拆分，將一個長數(shù)組的排序問題，拆分為兩個短數(shù)組的排序問題。
如果數(shù)組的長度最終變?yōu)?1 了，那么我們的拆分就表示已經(jīng)結(jié)束。
治：進(jìn)入合并階段，我們持續(xù)的將兩個有序的短數(shù)組合并為一個有序的長數(shù)組。我們可以用下圖演示這個過程。
可以感受到，基于分治策略的歸并排序，效率比冒泡排序更高。
代碼實(shí)現(xiàn)如下：
function sort(array) { const len = array.length if (len === 1) { return array } const middle = Math.floor(len / 2); const left = array.slice(0, middle); const right = array.slice(middle); console.log(right, sort(right)) return merge(sort(left), sort(right))}function merge(left, right) { var result = []; while(left.length && right.length) { if (left[0] <= right[0]) { result.push(left.shift()) } else { result.push(right.shift()) } } while(left.length) { result.push(left.shift()) } while(right.length) { result.push(right.shift()) } return result}當(dāng)我們通過前面的方式學(xué)習(xí)了分治策略之后，此時我們要去擴(kuò)展思考的就是：除了遞歸之外，我們還可以通過其他方式達(dá)到分治的目的。
例如桶排序。
當(dāng)我們需要處理的數(shù)據(jù)體量特別大時，桶排序就非常使用用來解決問題。
例如，我們有 100 條數(shù)據(jù)。
我們可以創(chuàng)建 10 個桶，并給每個桶標(biāo)記上合理的數(shù)字范圍。
分：遍歷 100 條數(shù)據(jù)，按照數(shù)字大小放入適合的桶中。
然后分別對每個桶中的數(shù)據(jù)進(jìn)行排序。
合：最后只需要依次將桶中的數(shù)據(jù)合并在一起即可。
實(shí)現(xiàn)代碼為：
function bucketSort(nums) { // 初始化 k = n/2 個桶 const k = nums.length / 2; const buckets = []; for (let i = 0; i < k; i++) { buckets.push([]); } // 1. 將數(shù)組元素分配到各個桶中 for (const num of nums) { // 輸入數(shù)據(jù)范圍為 [0, 1)，使用 num * k 映射到索引范圍 [0, k-1] const i = Math.floor(num * k); // 將 num 添加進(jìn)桶 i buckets[i].push(num); } // 2. 對各個桶執(zhí)行排序 for (const bucket of buckets) { // 使用內(nèi)置排序函數(shù)，也可以替換成其他排序算法 bucket.sort((a, b) => a - b); } // 3. 遍歷桶合并結(jié)果 let i = 0; for (const bucket of buckets) { for (const num of bucket) { nums[i++] = num; } }}尾調(diào)用是指在函數(shù)執(zhí)行中的最后一步操作調(diào)用函數(shù)。
function foo() { ... return bar()}如下案例，函數(shù)的最后一步操作是賦值操作，因此不是尾調(diào)用。
function foo() { let bar = fn(20) return bar}如下情況也不屬于尾調(diào)用，函數(shù)執(zhí)行的最后一步操作是 + 20。
function foo(num) { return bar(num) + 20}如下情況也不屬于尾調(diào)用，函數(shù)執(zhí)行的最后一步操作是 return undefined。
function foo(num) { bar(num)}我們需要注意的是，函數(shù)執(zhí)行中的最后一步操作，不一定是寫在最后一行代碼。例如：
// 這種也是屬于尾調(diào)用function named(m) { if (m < 29) { return bobo() } return coco()}在 ES6+ 中，當(dāng)我們啟用嚴(yán)格模式，就能啟用尾調(diào)用優(yōu)化。
尾調(diào)用優(yōu)化是指當(dāng)我們判斷情況是屬于尾調(diào)用時，之前的函數(shù)會直接出棧，而不會在始終在調(diào)用棧中占據(jù)位置。這樣，即使我們有大量的函數(shù)在調(diào)用，函數(shù)調(diào)用棧中的結(jié)構(gòu)也會依然簡潔。
例如下面這個案例。
function foo1() { console.log('foo1')}function foo2() { foo1()}function foo3() { foo2()}foo3()因為每個函數(shù)都不是尾調(diào)用，因此函數(shù)調(diào)用棧的入棧表現(xiàn)為。
我們調(diào)整一下寫法。
function foo1() { return console.log('foo1')}function foo2() { return foo1()}function foo3() { return foo2()}foo3()入棧表現(xiàn)為：
可以看到，尾調(diào)用優(yōu)化能大幅度的簡化調(diào)用棧在運(yùn)行時的結(jié)構(gòu)。能有效節(jié)省棧內(nèi)存，避免出現(xiàn)棧溢出的情況。
遞歸容易有棧溢出的風(fēng)險。因此尾調(diào)用優(yōu)化對于遞歸而言非常重要。但是要調(diào)整也比較簡單，我們只需要明確好怎么樣的寫法是尾調(diào)用即可。
例如，我們剛才的寫法，就不滿足尾調(diào)用的標(biāo)準(zhǔn)。因此我們需要調(diào)整一下。
function accumulation(min, max) { // 遞歸停止條件 if (max === min) { return min } // 拆解為同類子問題，并調(diào)用自身 return accumulation(min, max - 1) + max}我們可以調(diào)整為：
function accumulation(min, max, value = 0) { // 遞歸停止條件 if (max === min) { return min + value } let __value = value + max // 拆解為同類子問題，并調(diào)用自身 return accumulation(min, max - 1, __value)}這里有一個小細(xì)節(jié)需要注意一下，此時和前面的方案相比，我們調(diào)整了合并運(yùn)算的時機(jī)
我們可以看到，當(dāng)我們想要做到尾遞歸時，需要對實(shí)現(xiàn)思路有一個小的調(diào)整，以確保在遞歸調(diào)用的過程中，函數(shù)的最后一步是一個函數(shù)執(zhí)行，從而滿足尾調(diào)用優(yōu)化的條件。
最后，留給大家一個小小的思考題：結(jié)合記憶化與尾遞歸來實(shí)現(xiàn)斐波那契數(shù)列。
本文鏈接：http://www.tebozhan.com/showinfo-26-91160-0.html從基礎(chǔ)概念到進(jìn)階思考，完整的遞歸思維學(xué)習(xí)
聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請聯(lián)系：2376512515@qq.com 津ICP備18001702號
津公網(wǎng)安備 12010102000574號