一、递归

有一对兔子,从出生后第3个月起每个月生一对兔子,小兔子长到第3个月后每个月又生一对兔子,假如兔子不死,问第二十个月的兔子对数是多少?
我们来看一下，归纳一下：
* 第一个月: 1

  • 第二个月: 1

  • 第三个月: 2

  • 第四个月: 3

  • 第五个月: 5

…

这个问题是我们初中时候学过的斐波那契数列的兔子问题。
好的，作为一名前端程序猿，试问如何用js代码来解决这个问题。

  2.   // 此处做一下解释，为什么i是从2开始，而不是3,看循环体中代码，因为接收的参数num从第num-1个月开始，如果i从3开始算，那么得到的数据回事n的前一个月的数据，而不是当月数据。
  3.   //这里也可以将判断条件改为 <=,那么i就可以从di3个月算起了
  4. function fibs(num){
  5.   let n1 = 1 // 第1个月
  6.   let n2 = 1    // 第2个月的数量
  7.   let n = 1
  8.     for(let i = 2; i < num; i++){
  9.     [n1, n2] = [n2, n]
  10.     n = n1 + n2
  11.   }
  12.   return n
  13. }

上面的代码可能并不好理解，甚至还有同学对于数组的解构赋值不太了解，但是递归算法你一定可以一眼就看明白。

1、递归

递归，顾名思义是一种依次递增或者递减的归纳得来的算法。在学习递归前，我们先来说一下递归的两大要素：
1)终止条件
2)递归公式
尤其对于初学者而言，忘记终止条件，会导致循环持续下去，堆栈溢出，一般在chrome中会报错。
image.png

拿一个经典递归斐波那契数列来说，我们第一反应的fibs应该是这样的：

  1. function fibs(n) {
  2.   return n <3 ? 1 : fibs(n - 1) + fibs(n - 2)
  3. }

在这里 递归公式为 f(n) = f(n-1) + f(n-2)
终止条件为 n < 3（n===1 || n ===2 时候，返回都是1）

Good！这样计算固然没错，那么，这是不是最优解呢？
要讨论一个算法的优劣，毫无疑问，要看一下时间复杂度。这种粗暴递归的时间复杂度为O(2^n)

为什么是O(2^n)？我们以n=10举例。
来看下图！
fibs(10).png

通过上图，我们不仅可以看到，递归计算的复杂度，还可以看到在计算过程中，存在大量的重复计算！
What？
那想一下，我们能不能不去重复计算，怎么做。首先想到的方法——缓存

2、缓存递归

下面，我们来设置一个数组来缓存已经递归出的数据

  1. var cache = []
  2. function fibs(n) {
  3.   if(n < 3) {
  4.     return 1
  5.   } else {
  6.     if(!cache[n - 1]) {
  7.       cache[n-1] = fibs(n - 1)
  8.     }
  9.     if(!cache[n - 2]) {
  10.       cache[n-2] = fibs(n - 2)
  11.     }
  12.     return cache[n-1] + cache[n-2]
  13.   }
  14. }

通过以上方法将每一次递归的数据缓存在数组里，确实省去了一部分重复的计算。
重复计算去掉后，我们的时间复杂度变为多少了呢，应该是O(n)，因为此时的时间复杂度和数据规模呈正相关。没有了多余分枝树的计算。

3、动态规划

缓存递归已经算得上是很好的递归算法了，代码执行效率比较高。日常工作中，我一般写到缓存递归这一步，也就洋洋自得了，欧耶。确实，日常工作中写到缓存递归基本够用。
然而，这还不够。想要进阶，你必须知道，递归的逆向思维方式——动态规划。
我们先来说一说什么是动态规划。

  1. function fibs(n) {
  2.   let val = new Array(n).fill(1)
  3.   if (n <= 2) {
  4.     return 1
  5.   } else {
  6.     for (var i = 3; i <= n; ++i) {
  7.       val[i] = val[i-1] + val[i-2]
  8.     }
  9.     console.log(val)
  10.     return val[n - 1]
  11.   }
  12. }

二、递归的用途

1、对象、数组的深度复制

深度复制的原理是需要遍历对象，然后将得到的obj[key]赋值给新的对象，但是我们不能保证obj[key]为普通类型，必须判断当其为复杂类型时候，继续遍历obj[key]（也就是递归），直到我们得到一个普通类型数据。
这是我之前写的一段代码：

  1. // 判断数据类型
  2. const checkType = function(obj) {
  3.   return Object.prototype.toString.call(obj).slice(8, -1).toLowerCase()
  4. }
  6. // 判断为普通类型
  7. const isNoraml = function(obj) {
  8.   const type = checkType(obj)
  9.   if (type === 'number' || type === 'string' || type === 'null' || type === 'undefined') {
  10.       return true
  11.   }
  12.   return false
  13. }
  15. // 深度复制函数
  16. const deepClone = function(obj) {
  17.   let newObj = checkType(obj) === 'array' ? [] : {}
  18.   for(let key in obj){
  19.     // 由于for...in遍历继承属性，此处需要判断是不是对象的自身属性。在官方是不推荐用for...in遍历            数组的。此处也可根据类型，拆分为用for...in遍历对象，用for...of遍历数组。或者都用for循环遍历。
  20.     if(obj.hasOwnProperty(key)){
  21.       newObj[key] = isNoraml(obj[key]) ? obj[key]: deepClone(obj[key])
  22.     }
  23.   }
  24.   return newObj
  25. }

在网上也看到过有人这样写的，很简洁，贴出来。

  1. function deepClone(obj) {
  2.     let newObj = Array.isArray(obj) ? [] : {}
  3.     if (obj && typeof obj === "object") {
  4.         for (let key in obj) {
  5.             if (obj.hasOwnProperty(key)) {
  6.                 newObj[key] = (obj && typeof obj[key] === 'object') ? deepClone(obj[key]) : obj[key]
  7.             }
  8.         }
  9.     } 
  10.     return newObj
  11. }

感觉这个比我的写的好，哈哈哈。

当然，深度复制还有一些其他技巧，例如：

  1. JSON.parse(JSON.stringify(oldObj))
  2. // 该方法有很多缺点，大家可以自行查资料。

其过程说白了 就是利用JSON.stringify 将js对象序列化（JSON字符串），再使用JSON.parse来反序列化(还原)js对象。
缺点：
1、如果obj里面有时间对象，则JSON.stringify后再JSON.parse的结果，时间将只是字符串的形式。而不是时间对象；
2、如果obj里有RegExp、Error对象，则序列化的结果将只得到空对象；
3、如果obj里有函数，undefined，则序列化的结果会把函数或 undefined丢失；
4、如果obj里有NaN、Infinity和-Infinity，则序列化的结果会变成null
5、JSON.stringify()只能序列化对象的可枚举的自有属性，例如 如果obj中的对象是有构造函数生成的， 则使用JSON.parse(JSON.stringify(obj))深拷贝后，会丢弃对象的constructor；
6、如果对象中存在循环引用的情况也无法正确实现深拷贝；

以上缺点参考文章：https://blog.csdn.net/u013565133/article/details/102819929

  1. const newObj = Object.assign([],oldObj);
  2. // 该方法无法实现多级的深拷贝

在实际工作开发中，往往使用lodash插件，进行deeoClone。索性来看一下lodash源码怎么写的。我去cnd复制了lodash的源码。

image.png
在代码中搜索cloneDeep，发现是引用的函数baseClone,同时，传递了一个深度克隆的标记CLONE_DEEP_FLAG。

下面去看baseClone这个函数是怎么工作的。
image.png
我们先看数组吧，如果判断为数组，走 initCloneArray 方法，同时，下面判断，如果不是深度复制，则直接走copyArray方法，并return
我们再去看initCloneArray 方法做了什么：
image.png

我们看到，首先获取了数组长度
然后，创建了一个和array一样长度的空（new array.constructor(length)）
之后做了判断，

2、数组的扁平化

很多人用Array.prototype.flat去拍平一个多维数组，方便又好用。内部原理就是递归判断元素还是数组，接着遍历，直到为普通类型，将元素放入一个新的数组中。
看了上面的深度复制，稍微改造一下就可以得到一个flat方法。

  1. const checkType = function(obj) {
  2.   return Object.prototype.toString.call(obj).slice(8, -1).toLowerCase()
  3. }
  4. const isArray = function(obj) {
  5.   if (checkType(obj) === 'array') {
  6.       return true
  7.   }
  8.   return false
  9. }
  10. const arrayFlat = function(obj) {
  11.   let newArr = []
  12.   function flatData(obj) {
  13.     for(const key in obj){
  14.       if(obj.hasOwnProperty(key)){
  15.         isArray(obj[key]) ? flatData(obj[key]) : newArr.push(obj[key])
  16.       }
  17.     }
  18.     return newArr
  19.   }
  20.   return flatData(obj)
  21. }

上面为了方便使用的三元，其实都是不推荐的，if、else才是王道。当然，还可以继续优化，不在赘述。