無論是刷算法題，還是日常開發(fā)，遞歸都是一個(gè)非常常用的解決問題的思路。利用遞歸思維，我們可以使用少量的代碼解決復(fù)雜的問題。不過在剛開始的時(shí)候，遞歸通常沒有那么容易理解，我們就從圖示中的幾個(gè)方向，系統(tǒng)的為大家介紹遞歸的學(xué)習(xí)與運(yùn)用。

一、基礎(chǔ)概念

遞歸是一種迭代思維。是對(duì)復(fù)雜問題的一種拆解。如果我們重復(fù)的可以將問題拆解為同類型的子問題，那么，這就是一個(gè)可以使用遞歸的場(chǎng)景。

例如，現(xiàn)在我給你一個(gè)需求，需要你計(jì)算從 1 ～ 100 的所有數(shù)的總和。此時(shí)，我們可以對(duì)這個(gè)需求進(jìn)行拆解。

首先我們加入已經(jīng)定義好了一個(gè)方法，用來計(jì)算最小值遞增到最大值的數(shù)字總和。

function accumulation(min, max) {}

該方法目前只用于案例演示，語義上表示從 min 到 max 遞增數(shù)字的累加總和，無代碼實(shí)現(xiàn)，只有語義表達(dá)。

有了這個(gè)函數(shù)之后，我們可以把剛才的需求簡(jiǎn)單表示為 accumulation(1, 100)。

但是 accumulation(1, 100) 是一個(gè)復(fù)雜問題，我們可以將其拆解為：

accumulation(1, 99) + 100

拆解之后，我們需要解決的問題就稍微簡(jiǎn)單了一些，變成了 accumulation(1, 99) + 100。x + 100 就很簡(jiǎn)單，心算都能得出。但是 accumulation(1 + 99) 依然比較復(fù)雜，因此，我們可以重復(fù)剛才的思維，將拆解為。

accumulation(1, 98) + 99

重復(fù)下去，我們會(huì)發(fā)現(xiàn)，一個(gè)大的問題，最終會(huì)被我們拆解為。

accumulation(1, 97) + 98
accumulation(1, 96) + 97
...
accumulation(1, 2) + 3...

accumulation(1 + 2) 很容易能得出答案。

我們這里使用的是一個(gè)非?；A(chǔ)的例子來演示遞歸的思維，并非為了探討什么樣的計(jì)算方式來實(shí)現(xiàn)數(shù)字累加更合適。

二、基礎(chǔ)案例一

在代碼實(shí)現(xiàn)中，遞歸主要包含兩個(gè)部分。

• 函數(shù)調(diào)用自身。通過啟動(dòng)自身來執(zhí)行重復(fù)拆解問題的邏輯。
• 一個(gè)或者多個(gè)邊界條件，用于終止對(duì)自身的調(diào)用。

在上面的累加案例中，我們思考 accumulation(min, max) 的內(nèi)部實(shí)現(xiàn)。

首先邊界條件為：當(dāng) max 與 min 想等時(shí)，我們就沒必要繼續(xù)拆解下去了，此時(shí)，我們只需要返回 min 本身的值即可。

其他時(shí)候就調(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)算。在這個(gè)案例中，拆解的過程我們是從 accumulation(1, 100) 拆解到 accumulation(1, 1)，然后再回過頭來開始進(jìn)行運(yùn)算。

下面展示了該案例中，當(dāng)我們調(diào)用 accumulation(1, 100) 時(shí)的真實(shí)運(yùn)算過程。他與我們?cè)谒季S上做拆解的過程是反過來的。

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

因此，遞歸思維的強(qiáng)大之處就在于我們不需要花太多的精力把這個(gè)真實(shí)的運(yùn)算過程考慮得非常完善，計(jì)算機(jī)會(huì)幫我們做這個(gè)事情，而我們只需要知道如何拆解問題，就能最終把問題解決。

三、基礎(chǔ)案例二

在數(shù)學(xué)上有一個(gè)常見的概念，叫做斐波那契數(shù)列。它指的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21、...

它的規(guī)律為：當(dāng)前數(shù)字，總等于它前面兩個(gè)數(shù)字之和。我們需要封裝一個(gè)函數(shù)，用來計(jì)算第 n 個(gè)數(shù)字的斐波那契值是多少。

function fibonacci(n) {}

我們約定 n 是從 1 開始遞增的正整數(shù)。

首先思考邊界條件：當(dāng) n = 1 或者 n = 2 時(shí)，斐波那契值都是 1。

然后我們來拆解問題，例如我們要算 fibonacci(50)，按照規(guī)律，他就應(yīng)該等價(jià)于。

fibonacci(48) + fibonacci(49)

此時(shí)我們會(huì)發(fā)現(xiàn)，斐波那契數(shù)列的遞歸運(yùn)算過程要比剛才數(shù)字累加的計(jì)算復(fù)雜，但是我們并不需要關(guān)注它到底最后是如何計(jì)算的，我們只需要確保邊界條件和拆解思路是正確的即可，因此，思考到這里就可以直接給出代碼實(shí)現(xiàn)。

許多人在初學(xué)時(shí)理解不了遞歸是因?yàn)樗噲D在腦海中完整的呈現(xiàn)遞歸的壓棧過程，講道理，人腦能壓幾個(gè)棧啊 ～ ～

function fibonacci(n) {
  if (n == 1 || n == 2) {
    return 1
  }
  return fibonacci(n - 2) + fibonacci(n - 1)
}

當(dāng)然這樣會(huì)在傳入數(shù)字很大的時(shí)候存在過多的計(jì)算，因此這個(gè)場(chǎng)景使用遞歸來解決并非最好的方案，本文采用該案例只用于學(xué)習(xí)使用。

// rust 實(shí)現(xiàn)
fn fibonacci(n: i32) -> i32 {
  if n == 1 || n == 2 {
    return 1
  }
  fibonacci(n - 2) + fibonacci(n - 1)
}

四、遞歸進(jìn)階：記憶化

在上面我們對(duì)于斐波那契方案的解法中，雖然解決了問題，但是當(dāng)我傳入的 n 值變大時(shí)，會(huì)存在大量的冗余計(jì)算。

例如，當(dāng)我傳入 50，那么會(huì)遞歸的去算 fibonacci(48) 與 fibonacci(49)，但是，當(dāng)我們拆解 fibonacci(49) 時(shí)，又會(huì)再去算一次 fibonacci(48)。

這樣拆解下去，重復(fù)運(yùn)算的量非常大，因此我們需要想個(gè)辦法來解決這個(gè)問題。一個(gè)好的思路就是我們把算過的值找個(gè)地方存起來，下次遇到就直接從緩存中取值即可，而不用重復(fù)計(jì)算，因此我們把代碼改進(jìn)如下。

// 定義一個(gè)數(shù)組來緩存計(jì)算結(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)方式是我們?cè)谌肿兞恐?，定義了一個(gè)數(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 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))

五、遞歸進(jìn)階：分治策略

我們?cè)賮砘仡櫼幌逻f歸思維：重復(fù)的將問題拆分為同類型的子問題。完整來說，這是一個(gè)拆解 -> 直到觸發(fā)邊界終止條件 -> 運(yùn)算合并的過程。

我們可以用下圖來表達(dá)這個(gè)過程。

當(dāng)我們熟悉了這個(gè)基礎(chǔ)的遞歸思維之后，那么我們就可以對(duì)拆分方式于合并方式進(jìn)行進(jìn)一步的思考，以學(xué)習(xí)到更多的高級(jí)用法。

分治策略就是在遞歸的基礎(chǔ)之上，對(duì)拆分方式進(jìn)行調(diào)整演變出來的一種高效解題思路。我們以歸并排序?yàn)槔齺頌榇蠹抑v解分治策略。

歸并排序是一種對(duì)數(shù)組進(jìn)行快速排序的一種排序方式。

分：在拆分階段，我們通過遞歸從數(shù)組的中心位置進(jìn)行拆分，將一個(gè)長(zhǎng)數(shù)組的排序問題，拆分為兩個(gè)短數(shù)組的排序問題。

如果數(shù)組的長(zhǎng)度最終變?yōu)?1 了，那么我們的拆分就表示已經(jīng)結(jié)束。

治：進(jìn)入合并階段，我們持續(xù)的將兩個(gè)有序的短數(shù)組合并為一個(gè)有序的長(zhǎng)數(shù)組。我們可以用下圖演示這個(gè)過程。

可以感受到，基于分治策略的歸并排序，效率比冒泡排序更高。

代碼實(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í)體系擴(kuò)展

當(dāng)我們通過前面的方式學(xué)習(xí)了分治策略之后，此時(shí)我們要去擴(kuò)展思考的就是：除了遞歸之外，我們還可以通過其他方式達(dá)到分治的目的。

例如桶排序。

當(dāng)我們需要處理的數(shù)據(jù)體量特別大時(shí)，桶排序就非常使用用來解決問題。

例如，我們有 100 條數(shù)據(jù)。

我們可以創(chuàng)建 10 個(gè)桶，并給每個(gè)桶標(biāo)記上合理的數(shù)字范圍。

分：遍歷 100 條數(shù)據(jù)，按照數(shù)字大小放入適合的桶中。

然后分別對(duì)每個(gè)桶中的數(shù)據(jù)進(jìn)行排序。

合：最后只需要依次將桶中的數(shù)據(jù)合并在一起即可。

實(shí)現(xiàn)代碼為：

function bucketSort(nums) {
  // 初始化 k = n/2 個(gè)桶
  const k = nums.length / 2;
  const buckets = [];
  for (let i = 0; i < k; i++) {
    buckets.push([]);
  }
  // 1. 將數(shù)組元素分配到各個(gè)桶中
  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. 對(duì)各個(gè)桶執(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)用

尾調(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()
}

尾調(diào)用優(yōu)化

在 ES6+ 中，當(dāng)我們啟用嚴(yán)格模式，就能啟用尾調(diào)用優(yōu)化。

尾調(diào)用優(yōu)化是指當(dāng)我們判斷情況是屬于尾調(diào)用時(shí)，之前的函數(shù)會(huì)直接出棧，而不會(huì)在始終在調(diào)用棧中占據(jù)位置。這樣，即使我們有大量的函數(shù)在調(diào)用，函數(shù)調(diào)用棧中的結(jié)構(gòu)也會(huì)依然簡(jiǎn)潔。

例如下面這個(gè)案例。

function foo1() {
  console.log('foo1')
}

function foo2() {
  foo1()
}

function foo3() {
  foo2()
}

foo3()

因?yàn)槊總€(gè)函數(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)化能大幅度的簡(jiǎn)化調(diào)用棧在運(yùn)行時(shí)的結(jié)構(gòu)。能有效節(jié)省棧內(nèi)存，避免出現(xiàn)棧溢出的情況。

八、尾遞歸

遞歸容易有棧溢出的風(fēng)險(xiǎn)。因此尾調(diào)用優(yōu)化對(duì)于遞歸而言非常重要。但是要調(diào)整也比較簡(jiǎn)單，我們只需要明確好怎么樣的寫法是尾調(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)
}

這里有一個(gè)小細(xì)節(jié)需要注意一下，此時(shí)和前面的方案相比，我們調(diào)整了合并運(yùn)算的時(shí)機(jī)

我們可以看到，當(dāng)我們想要做到尾遞歸時(shí)，需要對(duì)實(shí)現(xiàn)思路有一個(gè)小的調(diào)整，以確保在遞歸調(diào)用的過程中，函數(shù)的最后一步是一個(gè)函數(shù)執(zhí)行，從而滿足尾調(diào)用優(yōu)化的條件。

最后，留給大家一個(gè)小小的思考題：結(jié)合記憶化與尾遞歸來實(shí)現(xiàn)斐波那契數(shù)列。