鴻蒙OS 4.0公測機型公布：甚至連nova6都支持
華為全新的HarmonyOS 4.0操作系統將于今天下午正式登場，官方在發布會之前也已經正式給出了可升級的機型產品，這意味著這些機型會率先支持升級享用。這次的HarmonyOS 4.0支持
無論是刷算法題，還是日常開發，遞歸都是一個非常常用的解決問題的思路。利用遞歸思維，我們可以使用少量的代碼解決復雜的問題。不過在剛開始的時候，遞歸通常沒有那么容易理解，我們就從圖示中的幾個方向，系統的為大家介紹遞歸的學習與運用。
遞歸是一種迭代思維。是對復雜問題的一種拆解。如果我們重復的可以將問題拆解為同類型的子問題，那么，這就是一個可以使用遞歸的場景。
例如，現在我給你一個需求，需要你計算從 1 ～ 100 的所有數的總和。此時，我們可以對這個需求進行拆解。
首先我們加入已經定義好了一個方法，用來計算最小值遞增到最大值的數字總和。
function accumulation(min, max) {}該方法目前只用于案例演示，語義上表示從 min 到 max 遞增數字的累加總和，無代碼實現，只有語義表達。
有了這個函數之后，我們可以把剛才的需求簡單表示為 accumulation(1, 100)。
但是 accumulation(1, 100) 是一個復雜問題，我們可以將其拆解為：
accumulation(1, 99) + 100拆解之后，我們需要解決的問題就稍微簡單了一些，變成了 accumulation(1, 99) + 100。x + 100 就很簡單，心算都能得出。但是 accumulation(1 + 99) 依然比較復雜，因此，我們可以重復剛才的思維，將拆解為。
accumulation(1, 98) + 99重復下去，我們會發現，一個大的問題，最終會被我們拆解為。
accumulation(1, 97) + 98accumulation(1, 96) + 97...accumulation(1, 2) + 3...accumulation(1 + 2) 很容易能得出答案。
我們這里使用的是一個非常基礎的例子來演示遞歸的思維，并非為了探討什么樣的計算方式來實現數字累加更合適。
在代碼實現中，遞歸主要包含兩個部分。
在上面的累加案例中，我們思考 accumulation(min, max) 的內部實現。
首先邊界條件為：當 max 與 min 想等時，我們就沒必要繼續拆解下去了，此時，我們只需要返回 min 本身的值即可。
其他時候就調用自身，因此，最終代碼實現為。
function accumulation(min, max) { // 遞歸停止條件 if (max === min) { return min } // 拆解為同類子問題，并調用自身 return accumulation(min, max - 1) + max}該方法的 rust 實現為。
如果你沒有學習過 rust，可跳過該部分，不影響 js 的學習。
fn accumulation(min: i32, max: i32) -> i32 { if min == max { return min; } accumulation(min, max - 1) + max}這里需要特別注意的是，遞歸的邏輯，是先拆解，后邏輯運算。在這個案例中，拆解的過程我們是從 accumulation(1, 100) 拆解到 accumulation(1, 1)，然后再回過頭來開始進行運算。
下面展示了該案例中，當我們調用 accumulation(1, 100) 時的真實運算過程。他與我們在思維上做拆解的過程是反過來的。
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因此，遞歸思維的強大之處就在于我們不需要花太多的精力把這個真實的運算過程考慮得非常完善，計算機會幫我們做這個事情，而我們只需要知道如何拆解問題，就能最終把問題解決。
在數學上有一個常見的概念，叫做斐波那契數列。它指的是這樣一個數列：1、1、2、3、5、8、13、21、...
它的規律為：當前數字，總等于它前面兩個數字之和。我們需要封裝一個函數，用來計算第 n 個數字的斐波那契值是多少。
function fibonacci(n) {}我們約定 n 是從 1 開始遞增的正整數。
首先思考邊界條件：當 n = 1 或者 n = 2 時，斐波那契值都是 1。
然后我們來拆解問題，例如我們要算 fibonacci(50)，按照規律，他就應該等價于。
fibonacci(48) + fibonacci(49)此時我們會發現，斐波那契數列的遞歸運算過程要比剛才數字累加的計算復雜，但是我們并不需要關注它到底最后是如何計算的，我們只需要確保邊界條件和拆解思路是正確的即可，因此，思考到這里就可以直接給出代碼實現。
許多人在初學時理解不了遞歸是因為他試圖在腦海中完整的呈現遞歸的壓棧過程，講道理，人腦能壓幾個棧啊 ～ ～
function fibonacci(n) { if (n == 1 || n == 2) { return 1 } return fibonacci(n - 2) + fibonacci(n - 1)}當然這樣會在傳入數字很大的時候存在過多的計算，因此這個場景使用遞歸來解決并非最好的方案，本文采用該案例只用于學習使用。
// rust 實現fn fibonacci(n: i32) -> i32 { if n == 1 || n == 2 { return 1 } fibonacci(n - 2) + fibonacci(n - 1)}在上面我們對于斐波那契方案的解法中，雖然解決了問題，但是當我傳入的 n 值變大時，會存在大量的冗余計算。
例如，當我傳入 50，那么會遞歸的去算 fibonacci(48) 與 fibonacci(49)，但是，當我們拆解 fibonacci(49) 時，又會再去算一次 fibonacci(48)。
這樣拆解下去，重復運算的量非常大，因此我們需要想個辦法來解決這個問題。一個好的思路就是我們把算過的值找個地方存起來，下次遇到就直接從緩存中取值即可，而不用重復計算，因此我們把代碼改進如下。
// 定義一個數組來緩存計算結果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]}這種實現方式是我們在全局變量中，定義了一個數組來緩存運算結果，很顯然，這并不是理想的實現。
我們需要調整寫法，將緩存數組搞到 fibonacci 內部中來。在 JavaScript 中，可以利用函數傳入引用數據類型的按引用傳遞特性，來達到引用數據的共享。
代碼實現如下：
// 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))我們再來回顧一下遞歸思維：重復的將問題拆分為同類型的子問題。完整來說，這是一個拆解 -> 直到觸發邊界終止條件 -> 運算合并的過程。
我們可以用下圖來表達這個過程。
當我們熟悉了這個基礎的遞歸思維之后，那么我們就可以對拆分方式于合并方式進行進一步的思考，以學習到更多的高級用法。
分治策略就是在遞歸的基礎之上，對拆分方式進行調整演變出來的一種高效解題思路。我們以歸并排序為例來為大家講解分治策略。
歸并排序是一種對數組進行快速排序的一種排序方式。
分：在拆分階段，我們通過遞歸從數組的中心位置進行拆分，將一個長數組的排序問題，拆分為兩個短數組的排序問題。
如果數組的長度最終變為 1 了，那么我們的拆分就表示已經結束。
治：進入合并階段，我們持續的將兩個有序的短數組合并為一個有序的長數組。我們可以用下圖演示這個過程。
可以感受到，基于分治策略的歸并排序，效率比冒泡排序更高。
代碼實現如下：
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}當我們通過前面的方式學習了分治策略之后，此時我們要去擴展思考的就是：除了遞歸之外，我們還可以通過其他方式達到分治的目的。
例如桶排序。
當我們需要處理的數據體量特別大時，桶排序就非常使用用來解決問題。
例如，我們有 100 條數據。
我們可以創建 10 個桶，并給每個桶標記上合理的數字范圍。
分：遍歷 100 條數據，按照數字大小放入適合的桶中。
然后分別對每個桶中的數據進行排序。
合：最后只需要依次將桶中的數據合并在一起即可。
實現代碼為：
function bucketSort(nums) { // 初始化 k = n/2 個桶 const k = nums.length / 2; const buckets = []; for (let i = 0; i < k; i++) { buckets.push([]); } // 1. 將數組元素分配到各個桶中 for (const num of nums) { // 輸入數據范圍為 [0, 1)，使用 num * k 映射到索引范圍 [0, k-1] const i = Math.floor(num * k); // 將 num 添加進桶 i buckets[i].push(num); } // 2. 對各個桶執行排序 for (const bucket of buckets) { // 使用內置排序函數，也可以替換成其他排序算法 bucket.sort((a, b) => a - b); } // 3. 遍歷桶合并結果 let i = 0; for (const bucket of buckets) { for (const num of bucket) { nums[i++] = num; } }}尾調用是指在函數執行中的最后一步操作調用函數。
function foo() { ... return bar()}如下案例，函數的最后一步操作是賦值操作，因此不是尾調用。
function foo() { let bar = fn(20) return bar}如下情況也不屬于尾調用，函數執行的最后一步操作是 + 20。
function foo(num) { return bar(num) + 20}如下情況也不屬于尾調用，函數執行的最后一步操作是 return undefined。
function foo(num) { bar(num)}我們需要注意的是，函數執行中的最后一步操作，不一定是寫在最后一行代碼。例如：
// 這種也是屬于尾調用function named(m) { if (m < 29) { return bobo() } return coco()}在 ES6+ 中，當我們啟用嚴格模式，就能啟用尾調用優化。
尾調用優化是指當我們判斷情況是屬于尾調用時，之前的函數會直接出棧，而不會在始終在調用棧中占據位置。這樣，即使我們有大量的函數在調用，函數調用棧中的結構也會依然簡潔。
例如下面這個案例。
function foo1() { console.log('foo1')}function foo2() { foo1()}function foo3() { foo2()}foo3()因為每個函數都不是尾調用，因此函數調用棧的入棧表現為。
我們調整一下寫法。
function foo1() { return console.log('foo1')}function foo2() { return foo1()}function foo3() { return foo2()}foo3()入棧表現為：
可以看到，尾調用優化能大幅度的簡化調用棧在運行時的結構。能有效節省棧內存，避免出現棧溢出的情況。
遞歸容易有棧溢出的風險。因此尾調用優化對于遞歸而言非常重要。但是要調整也比較簡單，我們只需要明確好怎么樣的寫法是尾調用即可。
例如，我們剛才的寫法，就不滿足尾調用的標準。因此我們需要調整一下。
function accumulation(min, max) { // 遞歸停止條件 if (max === min) { return min } // 拆解為同類子問題，并調用自身 return accumulation(min, max - 1) + max}我們可以調整為：
function accumulation(min, max, value = 0) { // 遞歸停止條件 if (max === min) { return min + value } let __value = value + max // 拆解為同類子問題，并調用自身 return accumulation(min, max - 1, __value)}這里有一個小細節需要注意一下，此時和前面的方案相比，我們調整了合并運算的時機
我們可以看到，當我們想要做到尾遞歸時，需要對實現思路有一個小的調整，以確保在遞歸調用的過程中，函數的最后一步是一個函數執行，從而滿足尾調用優化的條件。
最后，留給大家一個小小的思考題：結合記憶化與尾遞歸來實現斐波那契數列。
本文鏈接：http://www.tebozhan.com/showinfo-26-91160-0.html從基礎概念到進階思考，完整的遞歸思維學習
聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權所有 sitemap.xml
違法及侵權請聯系：2376512515@qq.com 津ICP備18001702號
津公網安備 12010102000574號