【愣锤笔记】一篇小短文彻底搞明白js的递归和尾递归

朴灿烈づ我的快乐病毒、 2022-01-19 00:57 208阅读 0赞

“我发起狠来连自己都打”这句话，其实有那么一丢丢递归的意思。好了，递归，什么是递归？**递归就是函数自己调用自己**。本文主要分两部分，第一部分讲的递归常用场景，第二部分讲递归带来的问题和解决方案。那么，?开始直击你灵魂深处的自虐之旅吧！

## 一、常见的递归操作 ##

递归的概念上面?已经说了，就是函数自己调用自己。这句话的意思也很明白，那么我们就看几个递归的实际例子，来探讨一下javascript中好玩的递归操作吧。

### 递归实现阶乘函数（1\*2\*3\*…\*n的值)    ###

先看下不通过递归的方式：

var factorial = function (n) {
      var result = 1;
      for (var i = 1; i <= n; i++) {
        result *= i;
      }
      return result;
    }
    console.log(factorial(5)) // 120复制代码

通过一个循环，实现来阶乘函数，老铁，没毛病！

下面看一下递归的方式实现阶乘函数：

var factorial = function (n) {
      if (n <= 1) return 1;
      return factorial(n - 1) * n;
    }
    console.log(factorial(5)) // 120复制代码

通过不停的调用自身，最终返回的是n \* （n - 1）\* (n - 2) …\* 2 \* 1就得出来我们想要结果。

### 经典的斐波那契数列：1，1，2，3，5，8，13……即从第三项起，每一项的值是前两项值的和。现在求第n项的值。    ###

var fibona = function (n) {
        // 如果求第一项或者第二项，则直接返回1
        if (n === 1 || n === 2) return 1;
        // 否则的话，返回前两项的和
        return fibona(n - 1) + fibona(n - 2);
    }
    console.log(fibona(4)) // 3复制代码

根据递归的思想，首先设置递归的终止条件，就是n=1或者n=2的时候返回1。否则的话就重复调用自身，即第n项的值是第n-1和第n-2项的和，那么同理，第n-1项的值是第n-1-2和n-1-1项的值，依次类推，通过递归，最终都转化成了f(1)或f(2)的值相加。

Tip：像斐波契数列这类的求值函数，计算量还是有些大的，所以我们完全可以做个缓存，在多次求相同的值的时候，我们可以直接从缓存取值。来吧，举个?：

// 有缓存的斐波那契数列函数
    var fibona = (function() {
        var cache = {};
        return function (n) {
          if (cache[n]) return cache[n];
          if (n === 1 || n === 2) return 1;
          return cache[n] = fibona(n - 1) + fibona(n - 2);
        }
    })();
    console.log(fibona(4)) // 3复制代码

利用闭包的思想，我们在闭包中定义一个缓存对象`cache`，将计算过的值存进该对象中。每次函数调用的时候，首先会从查看`cache`对象中是否已经存在这个值，有的话就直接返回，没有的话则重新计算。

### 递归实现深拷贝 ###

对象的深拷贝可是我们日常工作中很常用一个方法，几乎处处都有它的影子。常见的深拷贝方式有两种：

1.  利用json的方法
2.  遍历对象属性，然后依次赋值。如果值是引用类型，则继续遍历该值

// 利用json的深拷贝
    var deepClone = function (obj) {
      return JSON.parse(JSON.stringify(obj))
    }
    // 或这简写一下
    const deepClone = obj => JSON.parse(JSON.stringify(obj))复制代码

这种方法很简单，就是利用json的解析和序列化的两个方法。然鹅！曲项向天歌，白毛浮绿水，红掌拨清波 ! ! ! 原谅我，控制不住我自己呀～～～该方法只能对符合json格式的对象进行拷贝，而且属性值不能是函数等一些特殊类型。我是并不推荐使用这种方法作为项目基础函数库中的深拷贝方法的。?我们看下第二种深拷贝，也就是用递归来实现：

/**
     * 判断是不是对象(除null以外等对象类型)，这里isObject函数借鉴underscore中的实现
     * js中函数/数组/对象，都是对象类型
     */
    var isObject = function (obj) {
      var type = typeof obj;
      return type === 'function' || type === 'object' && !!obj;
    }
    // 定义深拷贝对象
    var deepClone = function (obj) {
        if (!isObject(obj)) return obj;
        var result = new obj.constructor();
        for (var i in obj) {
          if (obj.hasOwnProperty(i)) {
            result[i] = deepClone(obj[i]);
          }
        }
        return result;
    }
    // 打印拷贝效果
    console.log(deepClone([123, {a: 1, b: {c: 2}}, 456]))
    // 输出：
    [
        123,
        {
            a: 1,
            b: {
                c: 2
            }
        },
        456
    ]复制代码

*  首先说下这里的isObject对象，它判断一个数据是不是对象类型
 *  deepClone函数接收一个待克隆对象，并返回一个克隆后的对象
 *  deepClone函数首先判断是不是原始值（也就是`!isObject`)，如果是原始值则直接返回该原始值。如果不是原始值，则认为它是数组或者对象（这里忽略了函数/正则/日期等特殊数据类型，后面会介绍为什么）。然后通过`for/in`循环，通过递归调用自身进行赋值（递归调用的时候，如果是原始值则返回进行赋值，如果不是原始值则又进行`for/in`循环重复上面步骤）  
    
 *  另外说一点，这个函数里面，通过`new obj.constructor()`巧妙的避免了对当前数据是数组还是真对象的判断。

这个深拷贝函数是市面上很常见的深拷贝做法，基本覆盖了绝大部分的业务场景。但是它是有bug的，比如：对于属性值是`函数/日期对象/正则/环对象`（对象自己引用自己）等特殊类型，是有bug的。同样的json的那个深拷贝方法也是如此。

但是，还是那句话，该函数基本覆盖了我们日常拷贝需求，可以放心使用。如果你需要处理上述的这些特殊类型数据的话，该方法就行不通了。关于深拷贝的话题，仔细深聊下去，东西其实是蛮多的，完全可以单独拿出来讨论。本文旨在讲述递归，不深入讨论深拷贝了。如果有兴趣研究上述拷贝难题，可以查看lodash的深拷贝原理，或者MDN的结构化拷贝（也没有处理对函数的拷贝）。

### 递归遍历元素的所有子节点    ###

如果我们想遍历元素的所有子节点，我们可以通过递归非常方便的做到。

/**
     * 递归子节点，给每个元素节点添加'data-v-123456'属性 
     * @param {节点或元素} root 要递归的节点或元素
     * @param {Function} callback 每一次遍历的回调函数
     */
    const getChildNodes = (root, callback) => {
      // 判断是存在子元素
      if (root && root.children && root.children.length) {
        // 将子元素转换成可遍历的数组
        Array.from(root.children).forEach(node => {
          callback && typeof callback === 'function' && callback(node);
          // 递归子元素,重复上述操作
          getChildNodes(node, callback);
        });
    }
    // 例如，我们想像vue的scoped那样，为每一个html标签添加data-v-123456属性
    const root = document.getElementById('app');
    getChildNodes(root, function (node) {
      // 为每个子元素添加属性
      node.setAttribute('data-v-123456', '');
    });
    // 输出结果如下图复制代码

###  ###

*  二分法快速排序中的递归运用

二分法快排，或许是面试中常问到的数组排序方法。核心思想就是，从待排序数组中取出最中间的拿个值（注意，只是下标是中间的那个，并不是值是中间的那个），然后遍历剩余数组项，将比中间的值小的放在一个数组拼接在左边，比这个中间值大的全部放在一个数组然后拼接在右边。利用递归，知道每一次的数组个数只剩一项的时候，停止。如此，最终拼接出来的数组就是排序后的数组。

/**
     * 利用二分法快速排序
     */
    var quickSort = function (arr) {
      if (arr.length <= 1) return arr;
      var left = [],
      right = [],
      middle = arr.splice(Math.floor(arr.length / 2), 1)[0],
      i = 0,
      item;
      for (; item = arr[i++];) {
        item < middle ? left[left.length] = item : right[right.length] = item;
      }
      return quickSort(left).concat([middle], quickSort(right));
    }
    // 输出： [2, 3, 5]
    console.log(quickSort([3, 2, 5]))复制代码

### 树结构中可以使用递归    ###

树结构就是有个根结点，根结点底下可以有多个子节点，每个子节点又可以有子节点。常见的树结构数据如下：

var tree = {
      name: '电脑',
      children: [
        {
          name: 'F盘',
          children: [
            {
              name: '照片',
              children: []
            },
            {
              name: '文件',
              children: [
                {
                  name: '工作文件',
                  children: [
                    {
                      name: '报告',
                      children: []
                    }
                  ]
                }
              ]
            }
          ]      
        },
        {
          name: 'E盘',
          children: [
            {
              name: '视频',
              children: [
                {
                  name: 'js教程',
                  children: []
                }
              ]
            }
          ]
        }
      ]
    }复制代码

遍历树结构，有深度优先的原则，也有广度优先的原则。可以通过循环，也可以通过递归。接下来我们演示深度优先遍历。

所谓深度优先的原则：**就是顺着一个节点延伸下去，先遍历它的第一个子节点，然后是第一个孙节点，然后重孙节点，直到没有子节点为止**。即先纵深遍历完之后在遍历同级的其他节点。

// 深度优先的非递归遍历
    function deepTraversal (root, cb) {
      if (!root) return;
      cb && typeof cb === 'function' && cb(root);
      while (root.children && root.children.length) {
        var node = root.children.shift();
        cb && typeof cb === 'function' && cb(node);
        while (node && node.children && node.children.length) {
          root.children.unshift(node.children.pop());
        }
      }
    }
    // 调用，输出每一项的name值
    deepTraversal(tree, function (node) {
      console.log(node.name)；
    });
    // 输出:
    // 电脑
    // F盘
    // 照片
    // 文件
    // 工作文件
    // 报告
    // E盘
    // 视频
    // js教程复制代码

下面看下用递归如何来处理深度优先的遍历：

// 深度优先的递归遍历
    function deepTraversal (root, cb) {
      if (!root) return;
      cb && typeof cb === 'function' && cb(root);
      if (root.children && root.children.length) {
        var i = 0, node;
        for (; node = root.children[i++];) {
          deepTraversal(node, cb);
        }
      }
    }
    // 输出结果同上
    deepTraversal(tree, function (node) {
      console.log(node.name);
    });复制代码

通过上面的例子，虽然循环和递归都可以实现深度优先原则的遍历。但是使用循环的方式进行遍历，其实性能是更好的。

### 经典楼梯问题：一共10级楼梯，每次可以走一步或两步，求一共多少种走法 ###

这个问题，猛一看可能没有任何头绪。但是细细一想，要找出其中的规律。下面说下解题思路：若要到达最后一级楼梯（N=10）可以有两种走法：

1.  站在（N=8)的位置，然后迈两步上去，这是一种到达最顶的走法
2.  站在（N=9)的位置，然后迈一步上去，这是另一种到达最顶的走法

以此类推：

1.  若要到达(N=9)的位置，也有两种走法，即站在(N=8迈一步或者N=7迈两步）的位置上；
2.  若要到达(N=8)的位置，也有两种走法，即站在(N=7迈一步或者N=6迈两步）的位置上；

所以，可以理解为，若要到达第N级的走法有：到达第N-2的所有走法+到达N-1点所有走法。而到达N-1的走法有：到达N-1-2的所有走法+到达N-1-1的所有走法。结论来了，到达n级的所有走法：

fn = fn(n - 1) + f(n - 2) // 伪代码复制代码

照着这个思路，要到达某一级的所有走法等于到达前一级的所有走法加上到达前两级的所有走法之和。那总过有个下限吧。哎，你想对了，这个下限就是：

1.  如果你要到达第一级，那么走法只有一种
2.  如果你要到达第二级，走法有两种
3.  如果你要到达第三级，则又可以表示为到达第一级和到达第二级的所有走法之和了

所以，这个下限就是：

if (n === 1) return 1;
    if (n === 2) return 2;复制代码

这样，我们的求走法的函数也就顺着这个思路出来了：

var getRoutes = function (n) {
        if (n === 1) return 1;
        if (n === 2) return 2;
        return fibona(n - 1) + fibona(n - 2);
    }
    console.log(getRoutes(10)) // 89级复制代码

这个核心思想就是，到达某一级的走法永远等于到达前一级和前两级的所有走法之和。因此很适合用递归来处理。

### 细胞分裂问题：1个细胞，一个小时分裂一次，生命周期是3小时，求n小时后容器内，有多少细胞。 ###

这个题目的解题思路就是要分清细胞的状态，以及细胞的计算方式。粗略的说，细胞只有死亡和活着的状态，而最终求细胞个数也是指的求最后还活着的细胞。

由于细胞可以分裂，因此细胞可以细分为四种状态：

1.  刚分裂的状态----前一次（1/2/3状态）的新细胞（也包含最初的母细胞）才可以分裂成此状态
2.  分裂一小时的状态----只有前一次分裂的1状态的细胞分裂后自身会成为此状态
3.  分裂两小时的状态----只有前一次分裂的2状态的细胞再分裂后自身会成为此状态
4.  分裂三小时的状态（也是细胞的死亡状态）

因此，计算n小时后的细胞数，就是计算n小时后细胞状态为1/2/3的细胞总和。现在我们假设，求1状态的细胞总数的函数为funA，求2状态的为funB，求3状态的为funC。

最终我们的计算函数就是：

//获取n小时后的细胞总数
    var calcCells = function (n) {
        return funA(n) + funB(n) + funC(n)
    }复制代码

老铁，这样应该没毛病吧！

下面，重点在各个状态细胞的计算函数。

先来看1状态的细胞----刚分裂的细胞。前一次的1状态，前一次的2状态和前一次的3状态都可以分裂新细胞。而前一次的4状态则不可以。有人问，为啥？死了呀！难道还要诈尸呀～～还有一点，0小时的时候，1状态的细胞数量是1，就是这个母细胞。

由此：

// 获取1状态的细胞数量
    var funA = function (n) {
        if (n === 0) return 1;
        return funA(n - 1) + funB(n - 1) + funC(n - 1);
    }复制代码

再看2状态的细胞----分裂一小时的。2状态的细胞，只能是刚分裂状态的细胞，在一小时后变成此状态（也就是前一次分裂状态为1的细胞）。但是，在0小时的时候，是没有此状态的细胞。所以：

// 获取2状态的细胞数量
    var funB = function (n) {
        if (n === 0) return 0;
        return funA(n - 1);
    }复制代码

同理，3状态的细胞，则是由2状态的细胞在一小时变成的，so：

// 获取3状态的细胞数量
    var funC = function (n) {
        if (n === 0 || n === 1) return 0;
        return funB(n - 1);
    }复制代码

这样，我们利用递归便实现该方法：

console.log(fibo(1), fibo(2), fibo(3), fibo(4), fibo(5)) // 2 4 7 13 24复制代码

## 二、递归的问题和优化 ##

前面讲了这么多有趣的递归，然而，递归并非完美的！不仅如此，还会有性能和内存问题。最经典的莫过于堆栈溢出。在讲递归的问题之前，我们先了解几个概念：

1.  堆栈：后进先出的原则。想象一下桌子上放一堆书，先放的在最底下，后放的在最顶部，拿书的时候，后放的被先拿走。即后进入堆栈的先出栈。
2.  函数的堆栈概念：js中，每次函数调用会在内存形成一个“调用记录”， 保存着调用位置和内部变量等信息。如果函数中调用了其他函数，则js引擎将其运行过程暂停，去执行新调用的函数，新调用函数成功后继续返回当前函数的执行位置，继续往后执行。执行新调用的函数过程，也是将其推入到堆栈的最顶部并为其开辟一块内容。新函数执行完毕后将其推出堆栈，并回收内存。由此便形成了函数的堆栈。

了解了这些概念之后，我们再来看这个阶乘函数。

// 经典的阶乘函数
    var factorial = function (n) {
        if (n <= 1) return 1;
        return factorial(n - 1) * n
    }
    console.log(factorial(5)) // 120
    console.log(factorial(6594)) // 6594爆栈复制代码

输出结果我们看到，在递归近7000次的时候，堆栈溢出了（注意：这个数字毫无意义，不是w3c规范规定的，而是js的解释器定的，根据**不同的平台/不同的浏览器/不同的版本**可能都会不一样）。错误结果如下图所示，之所以浏览器会如此蛮横加个溢出，强制终止掉你的递归，是为了包含你的系统因为不当的程序而被耗尽内存。

为什么会堆栈溢出呢？从上面的概念我们理解到，每次函数调用，都会为其开辟一小块内存，并把函数推入堆栈，执行完毕后才会释放。而我们的阶乘函数，在最后一句return factorial(n - 1) \* n 包含了一个对自身的调用 \* n，这就使得该函数必须要等待新的函数调用执行完毕后再乘以n之后才算执行完毕返回，同样的新的函数调用在最后的时候又要等待内部的新的函数嗲调用执行完毕后进行计算再返回。如此一来，就好比如，a内有个b，b有个c，c内有个d……而a要等b执行完才释放，b要等c，c要等d……这样在堆栈内便存放了n多个函数的“调用记录”，而每一个“调用记录”是开辟了一块内存的，所以，便超出了浏览器的限制，溢出了。

知道了问题，那解决办法呢？办法就是**尾调用优化**。

尾调用就是：**在函数执行的最后一步返回一个一个函数调用**。这个概念很简单，我们看下几个例子：

/**
     * 函数最后一行虽然是一个函数调用，然后并未返回
     * funA函数会等funB执行完毕后才算执行完毕，才能被推出栈。
     * 所以不是尾调用
     */
    function funA () {
      funB();
    }
    
    /**
     * 函数执行到最后一行，需要等到funB执行完毕的结果，然后funA再计算后才返回结果
     */
    function funA () {
      var x = 10;
      return x + funB();
    }
    
    /**
     * 在funB执行完毕后还有赋值操作，因此也不是尾调用
     * 本质因为要等funB执行完毕后funA才能执行完毕
     */
    function funA () {
      var x = funB();
      return x;
    }复制代码

以上这些都不是尾调用，原因都写在注释了。下面再看下是尾调用的几种情况：

// 函数最后的一行返回了一个函数调用
    function func () {
        // 省略函数的逻辑
        // ……
        return funA()
    }
    // 函数通过判断，最后还是返回的函数调用
    function func () {
        // 省略函数的逻辑
        // ……
        var x = 0;
        if (x >= 0) return funB()
        return funA()
    }
    // 虽然最后一行是一个三元运算符，但是最终返回的也是一个函数调用
    function func () {
        // 省略函数的逻辑
        // ……
        return  0 > 1 ? funA() : funB();
    }复制代码

尾调用的核心就是：在函数执行的最后一步返回一个函数调用。注意哦，是最后一步，而不必须是最后一行代码。

知道了尾调用的核心思想，我们回过头再来看一下我们的阶乘函数，若要达到最后一步只返回一个函数调用，那我们就要想办法去掉函数返回中的`*n`这块。

由此，我们可以在函数的参数中，携带一个sum参数来存放每一次递归后的值，最后在递归到1的时候，将这参数返回即可！ok，下面我们来实现：

// 使用了一个参数sum来保存阶乘后的值
    // 函数执行到n==1的时候，返回sum的值
    var factorial = function (n, sum) {
        if (n <= 1) return sum;
        return factorial(n - 1, sum * n)
    }
    console.log(factorial(5, 1)) // 120
    console.log(factorial(12040, 1)) // 12000左右依然爆栈了，但是比之前的爆栈上限提升了不少复制代码

我们每次递归调用的时候，把当前的计算结果存在函数的第二个参数sum中，并传递给下一次的递归调用，知道最后n===1的时候，返回最终的结果。

但是，现在的这种调用方法，我们每次都需要加一个默认的参数1，感觉好麻烦哦！心里好不爽！怎么办？当然是盘他啊，给他干掉。

*  可以直接写个新的接口，返回factorial函数的调用，把1这个参数给他带上

var newFactorial = function(n) {
       return factorial(n, 1)
    };复制代码

*  函数携带默认参数的做法，最简单的莫过于es6本身支持的特性----函数参数设置默认值：

var factorial = function (n, sum = 1) {
        if (n <= 1) return sum;
        sum *= n;
        return factorial(n - 1, sum)
    }复制代码

*  最后，我个人更推荐的是通过向右柯里化的方式，这是函数式编程的一个很重要的概念。

// 通过写一个向右柯里化函数来封装新的阶乘函数
    var curry = function (fn, sum) {
        return function (n) {
          return fn.call(fn, n, sum);
        }
    }
    var curryFactorial = curry(factorial, 1);
    console.log(curryFactoial(5)) // 120复制代码

通过curry函数，对阶乘函数进行来封装，返回一个新的带默认参数sum为1的新函数。关于柯里化函数，有兴趣的小伙伴可以去研究研究，也很有意思的呦。

注意：我们虽然通过了尾调用优化了我们的递归函数（这里是尾递归，尾调用自身即尾递归），但是上面的操作，在达到某个值的时候依然会爆栈。这是为什么呢？究其原因：

*  尾调用只在严格模式下生效，正常模式下是没有效果的  
    
 *  es6明确表示，只要实现了尾调用，就不会栈溢出。然后js解释器在实现的时候并未遵守这一规范。v8曾经实现过，后来又删除了调用优化，因为进行函数尾递归优化之后，会破坏函数的调用栈记录。w3c也在致力于寻找新的语法来指明函数的尾调用。

最后，还要再说明几点：

*  递归本质就是自己调用自己，在终止条件前会一直递归。在递归层级到一定程度时，会出现栈溢出而停止递归。
 *  由于递归存在一些性能和内存的问题，我们要在使用递归时需要更加慎重。但并不是不能使用递归，递归还是有很多其适宜的使用场景。
 *  通常我们在客户端的编程，也基本不会涉及到需要递归成千上万的层级，所以在确保不会触碰到这些阀值前，还是可以安心使用的。
 *  在客户端编程的时候，所需要考虑的性能问题，更多的不在语言层面，因此，我们有些是更需要关注写出来的代码的可读性和可维护性。

转载于:https://juejin.im/post/5c9a0941e51d45494923ab46