您好，我是沧沧凉凉，是一名前端开发者，目前在掘金、知乎以及个人博客上同步发表一些学习前端时遇到的趣事和知识，欢迎关注。

---

一般来讲，前端对于算法和数据结构的理解往往是不如后端的，如果你不立志成为一个架构师，而是进行普通的业务开发，那么前端使用到算法的场景并不是太多，大多都是由后端将数据处理好后，前端只需要做一些判断和展示。

但你想要深入学习一门框架（没错，说的就是React），想要读懂框架的源码，那么算法就是你必不可少的知识，因为很多框架中会大量使用到各种算法。

所以本系列文章就是我自己从一个前端开发者的角度出发，阅读一些算法书籍，并且将书籍中学到的知识分享出来，因为一本书往往有上百页，很多人捧起书完全就没有翻阅的动力，而本系列文章争取每篇都将字数控制在千字左右，读起来更加的轻松。

递归

我们先看一下递归函数长成什么样子，比如写一个斐波那契打印函数：

function fibonacci(first, second) {
  const a = second;
  const b = first + second;
  // 打印斐波那契数列
  console.log(a);
  // 递归调用
  fibonacci(a, b);
}

fibonacci(0, 1);

斐波那契数列即为：由0和1开始，之后的斐波那契数就是由之前的两数相加而得出。

上面的代码运行后的：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 ,610, 987……，但是该函数由于没有推出条件，会一直递归下去。

所以递归即函数内部自己调用自己，使用递归可以大幅度的简化代码，但如果使用不当也会造成死循环，而且递归往往会存在一些维护上的困难（别人理解起来有困难）。

编写递归函数时，必须告诉它何时停止递归。正因为如此，每个递归函数都有两部分∶基线条件（base case）和递归条件（recursive case）。

递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。

基线条件是非常重要的，上面的函数中就没有基线条件，所以该函数会一直运行下去，直到占满内存程序崩溃。

给上面的函数加上基线条件：

function fibonacci(first, second) {
  const a = second;
  // 基线条件
  if (a > 46368) {
  }
  // 递归条件
  else {
    const b = first + second;
    // 打印斐波那契数列
    console.log(a);
    // 递归调用
    fibonacci(a, b);
  }
}

才接触递归的朋友总有一种想完全搞清楚递归的运行过程，其实在使用递归的过程中，我们只需要写好基线条件（base case）和递归条件（recursive case），至于代码具体是如何进行运行的，其实我们不用太过于关心，即我们只需要关注递归条件，而不需要关注递归调用。

比如上面的斐波那契函数，我们只需要关注：

const b = first + second;
// 打印斐波那契数列
console.log(a);

并不需要关注后面的递归调用fibonacci(a, b)，只要你的递归条件编写正确，后面的递归调用就一定会得到你想要的结果，我最开始接触递归的时候就喜欢一层一层的去想递归调用中会得到的值，比如第二次递归调用会得到1，第三次递归调用会得到2，第4次递归调用会得到3…这样一层一层的去想，很容易就将你自己卡住，陷入递归中。

栈

说了这么多，还是上面的斐波那契打印函数，之前我们打印的值是1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 ,610, 987……，如果我们这次要从后往前打印呢？

即要打印出…987, 610, 377, 233, 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1，这又该怎么办呢？仔细看下面更改后的函数：

function fibonacci(first, second) {
  const a = second;
  // 基线条件
  if (a > 46368) {
  }
  // 递归条件
  else {
    const b = first + second;
    // 递归调用
    fibonacci(a, b);
    // 打印斐波那契数列（变更了位置）
    console.log(a);
  }
}

fibonacci(0, 1);

咋一看是不是跟上面的函数差不多？只是将console.log(a);写到了递归调用下面，这个时候你再尝试运行一下代码，你就会发现已经从后往前开始打印斐波那契数列了，是不是非常的神器？该例子很好的反映上面的调用栈的问题。

最后

在我们编写应用的过程中，时不时会用到递归，但是！不推荐用递归替代循环，因为所有函数的调用都会进入调用栈，如果调用栈很长的话会占用大量的内存，而且大量使用递归会使得代码变得难以维护。

这里还有一篇React中创建递归组件，可以看看如何在React中使用递归组件来简化你的代码。