從基礎概念到進階思考，完整的遞歸思維學習
無論是刷算法題，還是日常開發(fā)，遞歸都是一個非常常用的解決問題的思路。利用遞歸思維，我們可以使用少量的代碼解決復雜的問題。不過在剛開始的時候，遞歸通常沒有那么容易理解，我們就從圖示中的幾個方向，系統(tǒng)的為大家介紹遞歸的學習與運用。
一、基礎概念
遞歸是一種迭代思維。是對復雜問題的一種拆解。如果我們重復的可以將問題拆解為同類型的子問題，那么，這就是一個可以使用遞歸的場景。
例如，現(xiàn)在我給你一個需求，需要你計算從 1 ～ 100 的所有數(shù)的總和。此時，我們可以對這個需求進行拆解。
首先我們加入已經定義好了一個方法，用來計算最小值遞增到最大值的數(shù)字總和。
function accumulation(min, max) {}該方法目前只用于案例演示，語義上表示從 min 到 max 遞增數(shù)字的累加總和，無代碼實現(xiàn)，只有語義表達。
有了這個函數(shù)之后，我們可以把剛才的需求簡單表示為 accumulation(1, 100)。
但是 accumulation(1, 100) 是一個復雜問題，我們可以將其拆解為：
accumulation(1, 99) + 100拆解之后，我們需要解決的問題就稍微簡單了一些，變成了 accumulation(1, 99) + 100。x + 100 就很簡單，心算都能得出。但是 accumulation(1 + 99) 依然比較復雜，因此，我們可以重復剛才的思維，將拆解為。
accumulation(1, 98) + 99重復下去，我們會發(fā)現(xiàn)，一個大的問題，最終會被我們拆解為。
accumulation(1, 97) + 98
accumulation(1, 96) + 97
...
accumulation(1, 2) + 3...accumulation(1 + 2) 很容易能得出答案。
我們這里使用的是一個非常基礎的例子來演示遞歸的思維，并非為了探討什么樣的計算方式來實現(xiàn)數(shù)字累加更合適。
二、基礎案例一
在代碼實現(xiàn)中，遞歸主要包含兩個部分。
- 函數(shù)調用自身。通過啟動自身來執(zhí)行重復拆解問題的邏輯。
- 一個或者多個邊界條件，用于終止對自身的調用。
在上面的累加案例中，我們思考 accumulation(min, max) 的內部實現(xiàn)。
首先邊界條件為：當 max 與 min 想等時，我們就沒必要繼續(xù)拆解下去了，此時，我們只需要返回 min 本身的值即可。
其他時候就調用自身，因此，最終代碼實現(xiàn)為。
function accumulation(min, max) {
// 遞歸停止條件
if (max === min) {
return min
}
// 拆解為同類子問題，并調用自身
return accumulation(min, max - 1) + max
}該方法的 rust 實現(xiàn)為。
如果你沒有學習過 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) -> 1
accumulation(1, 2) -> accumulation(1, 1) + 2 -> 3
accumulation(1, 3) -> accumulation(1, 2) + 3 -> 6
accumulation(1, 4) -> accumulation(1, 3) + 4 -> 10
...
accumulation(1, 97) -> accumulation(1, 96) + 97 -> 4753
accumulation(1, 98) -> accumulation(1, 97) + 98 -> 4851
accumulation(1, 99) -> accumulation(1, 98) + 99 -> 4950
accumulation(1, 100) -> accumulation(1, 99) + 100 -> 5050因此，遞歸思維的強大之處就在于我們不需要花太多的精力把這個真實的運算過程考慮得非常完善，計算機會幫我們做這個事情，而我們只需要知道如何拆解問題，就能最終把問題解決。
三、基礎案例二
在數(shù)學上有一個常見的概念，叫做斐波那契數(shù)列。它指的是這樣一個數(shù)列：1、1、2、3、5、8、13、21、...
它的規(guī)律為：當前數(shù)字，總等于它前面兩個數(shù)字之和。我們需要封裝一個函數(shù)，用來計算第 n 個數(shù)字的斐波那契值是多少。
function fibonacci(n) {}我們約定 n 是從 1 開始遞增的正整數(shù)。
首先思考邊界條件：當 n = 1 或者 n = 2 時，斐波那契值都是 1。
然后我們來拆解問題，例如我們要算 fibonacci(50)，按照規(guī)律，他就應該等價于。
fibonacci(48) + fibonacci(49)此時我們會發(fā)現(xiàn)，斐波那契數(shù)列的遞歸運算過程要比剛才數(shù)字累加的計算復雜，但是我們并不需要關注它到底最后是如何計算的，我們只需要確保邊界條件和拆解思路是正確的即可，因此，思考到這里就可以直接給出代碼實現(xiàn)。
許多人在初學時理解不了遞歸是因為他試圖在腦海中完整的呈現(xiàn)遞歸的壓棧過程，講道理，人腦能壓幾個棧啊 ～ ～
function fibonacci(n) {
if (n == 1 || n == 2) {
return 1
}
return fibonacci(n - 2) + fibonacci(n - 1)
}當然這樣會在傳入數(shù)字很大的時候存在過多的計算，因此這個場景使用遞歸來解決并非最好的方案，本文采用該案例只用于學習使用。
// rust 實現(xiàn)
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)。
這樣拆解下去，重復運算的量非常大，因此我們需要想個辦法來解決這個問題。一個好的思路就是我們把算過的值找個地方存起來，下次遇到就直接從緩存中取值即可，而不用重復計算，因此我們把代碼改進如下。
// 定義一個數(shù)組來緩存計算結果
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]
}這種實現(xiàn)方式是我們在全局變量中，定義了一個數(shù)組來緩存運算結果，很顯然，這并不是理想的實現(xiàn)。
我們需要調整寫法，將緩存數(shù)組搞到 fibonacci 內部中來。在 JavaScript 中，可以利用函數(shù)傳入引用數(shù)據(jù)類型的按引用傳遞特性，來達到引用數(shù)據(jù)的共享。
代碼實現(xiàn)如下：
// Implement it with js
function 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 rust
struct 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ā)邊界終止條件 -> 運算合并的過程。
我們可以用下圖來表達這個過程。
當我們熟悉了這個基礎的遞歸思維之后，那么我們就可以對拆分方式于合并方式進行進一步的思考，以學習到更多的高級用法。
分治策略就是在遞歸的基礎之上，對拆分方式進行調整演變出來的一種高效解題思路。我們以歸并排序為例來為大家講解分治策略。
歸并排序是一種對數(shù)組進行快速排序的一種排序方式。
分：在拆分階段，我們通過遞歸從數(shù)組的中心位置進行拆分，將一個長數(shù)組的排序問題，拆分為兩個短數(shù)組的排序問題。
如果數(shù)組的長度最終變?yōu)?1 了，那么我們的拆分就表示已經結束。
治：進入合并階段，我們持續(xù)的將兩個有序的短數(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
}六、知識體系擴展
當我們通過前面的方式學習了分治策略之后，此時我們要去擴展思考的就是：除了遞歸之外，我們還可以通過其他方式達到分治的目的。
例如桶排序。
當我們需要處理的數(shù)據(jù)體量特別大時，桶排序就非常使用用來解決問題。
例如，我們有 100 條數(shù)據(jù)。
我們可以創(chuàng)建 10 個桶，并給每個桶標記上合理的數(shù)字范圍。
分：遍歷 100 條數(shù)據(jù)，按照數(shù)字大小放入適合的桶中。
然后分別對每個桶中的數(shù)據(jù)進行排序。
合：最后只需要依次將桶中的數(shù)據(jù)合并在一起即可。
實現(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 添加進桶 i
buckets[i].push(num);
}
// 2. 對各個桶執(zhí)行排序
for (const bucket of buckets) {
// 使用內置排序函數(shù)，也可以替換成其他排序算法
bucket.sort((a, b) => a - b);
}
// 3. 遍歷桶合并結果
let i = 0;
for (const bucket of buckets) {
for (const num of bucket) {
nums[i++] = num;
}
}
}七、尾調用
尾調用是指在函數(shù)執(zhí)行中的最后一步操作調用函數(shù)。
function foo() {
...
return bar()
}如下案例，函數(shù)的最后一步操作是賦值操作，因此不是尾調用。
function foo() {
let bar = fn(20)
return bar
}如下情況也不屬于尾調用，函數(shù)執(zhí)行的最后一步操作是 + 20。
function foo(num) {
return bar(num) + 20
}如下情況也不屬于尾調用，函數(shù)執(zhí)行的最后一步操作是 return undefined。
function foo(num) {
bar(num)
}我們需要注意的是，函數(shù)執(zhí)行中的最后一步操作，不一定是寫在最后一行代碼。例如：
// 這種也是屬于尾調用
function named(m) {
if (m < 29) {
return bobo()
}
return coco()
}尾調用優(yōu)化
在 ES6+ 中，當我們啟用嚴格模式，就能啟用尾調用優(yōu)化。
尾調用優(yōu)化是指當我們判斷情況是屬于尾調用時，之前的函數(shù)會直接出棧，而不會在始終在調用棧中占據(jù)位置。這樣，即使我們有大量的函數(shù)在調用，函數(shù)調用棧中的結構也會依然簡潔。
例如下面這個案例。
function foo1() {
console.log('foo1')
}
function foo2() {
foo1()
}
function foo3() {
foo2()
}
foo3()因為每個函數(shù)都不是尾調用，因此函數(shù)調用棧的入棧表現(xiàn)為。
我們調整一下寫法。
function foo1() {
return console.log('foo1')
}
function foo2() {
return foo1()
}
function foo3() {
return foo2()
}
foo3()入棧表現(xiàn)為：
可以看到，尾調用優(yōu)化能大幅度的簡化調用棧在運行時的結構。能有效節(jié)省棧內存，避免出現(xiàn)棧溢出的情況。
八、尾遞歸
遞歸容易有棧溢出的風險。因此尾調用優(yōu)化對于遞歸而言非常重要。但是要調整也比較簡單，我們只需要明確好怎么樣的寫法是尾調用即可。
例如，我們剛才的寫法，就不滿足尾調用的標準。因此我們需要調整一下。
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)
}這里有一個小細節(jié)需要注意一下，此時和前面的方案相比，我們調整了合并運算的時機
我們可以看到，當我們想要做到尾遞歸時，需要對實現(xiàn)思路有一個小的調整，以確保在遞歸調用的過程中，函數(shù)的最后一步是一個函數(shù)執(zhí)行，從而滿足尾調用優(yōu)化的條件。
最后，留給大家一個小小的思考題：結合記憶化與尾遞歸來實現(xiàn)斐波那契數(shù)列。
