从基础概念到进阶思考，完整的递归思维学习

无论是刷算法题，还是日常开发，递归都是一个非常常用的解决问题的思路。利用递归思维，我们可以使用少量的代码解决复杂的问题。不过在刚开始的时候，递归通常没有那么容易理解，我们就从图示中的几个方向，系统的为大家介绍递归的学习与运用。

一、基础概念

递归是一种迭代思维。是对复杂问题的一种拆解。如果我们重复的可以将问题拆解为同类型的子问题，那么，这就是一个可以使用递归的场景。

例如，现在我给你一个需求，需要你计算从 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) + 98
accumulation(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) -> 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

因此，递归思维的强大之处就在于我们不需要花太多的精力把这个真实的运算过程考虑得非常完善，计算机会帮我们做这个事情，而我们只需要知道如何拆解问题，就能最终把问题解决。

三、基础案例二

在数学上有一个常见的概念，叫做斐波那契数列。它指的是这样一个数列：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 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
}

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]  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)
}

这里有一个小细节需要注意一下，此时和前面的方案相比，我们调整了合并运算的时机

我们可以看到，当我们想要做到尾递归时，需要对实现思路有一个小的调整，以确保在递归调用的过程中，函数的最后一步是一个函数执行，从而满足尾调用优化的条件。

最后，留给大家一个小小的思考题：结合记忆化与尾递归来实现斐波那契数列。