前端递归思想（禁止套娃）

什么是递归

所谓递归，就是在程序中函数直接或间接地调用了自己，听起来好像会导致无限重复，但只要定义适当，就不会这样。一般来说，一个递归函数的定义有两个部分。首先，至少要有一个底线，就是一个临界条件，越过此处，则递归

那么如何写出递归呢，无非分以下几步：

写出递归公式
找到临界条件

举个🌰

Fibonacci数列

1 1 2 3 5 8 13 ... 求第n项

按照之前说的方法，首先，找出递归关系

f(n) = f(n - 1) + f(n - 2)

显然，临界条件为

f(1) = 1, f(2) = 1

最后得到方法

function fib(n){
   if(n == 0 || n ==1) return 1;
   return fib(n-1) + fib(n-2);
 }

如上所示，能完成一个简单的递归函数，不过要写好递归还是需要注意很多东西的

递归的注意事项

爆栈

函数调用会使用栈来保存临时变量，而栈的数据结构为先进后出，每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。

限制递归层级

如上述的fib(n)函数，如果递归的层级过深，则会导致爆栈，为了防止爆栈，其一的方法就是限制其递归的层级，如下

let depth = 0
function fib(n){
   ++depth
   if (depth > 1000) throw exception
   if(n == 0 || n ==1) return 1;
   return fib(n-1) + fib(n-2);
}

尾递归优化

另外一种方法则是尾递归优化以上述fib(n)函数为例，加入两个临时变量来存储得到的值

function fib(n, ac1 = 0, ac2 = 1){
   if(n == 0) {
       return ac1
   } else {
       return (n - 1, ac2 , ac1 + ac2)
   }
}

但尾递归优化的提案并没有完全通过，而且尾递归优化存在下述两个问题

在引擎层面进行尾调优化是一个隐式行为，如果代码存在死循环尾递归调用，可能因为优化后没有爆栈报错提示而无法被开发者察觉
优化后，调用堆栈信息会丢失，造成调试困难

Trampolining（蹦床函数）

在没有对尾递归优化支持的情况下，可以使用蹦床函数替代，什么是蹦床函数呢，举个🌰

function trampoline(f) {
 while (f && f instanceof Function) {
   f = f();
 }  
 return f;
}

trampoline 方法中，如果 f 是个函数就一直调用到返回不是函数为止，注意这种方式不是递归调用，而是循环，不会增加调用栈。

我们尝试把上边的例子改写成使用 Trampolining

function trampoline(f) {
 while (f && f instanceof Function) {
   f = f();
 }  
 return f;
}

function fTrampoline (n, ac1=0, ac2=1){
   if(n===0){
   return ac1
 }else{
   return fTrampoline.bind(null, n-1, ac2, ac1+ac2)
 }
}

// 结合两个函数进行调用
trampoline(fTrampoline(10000))

重复计算

还是上面的那个🌰，fib(n -1) + fib(n -2)由这个递归公式不难看出f(5) = f(4) + f(3)，而f(4) = f(3) + f(2)由此可见，会出现很多类似于f(3)这样的重复计算，那么如何避免此类的重复计算呢，就JS而言，可以使用set weakMap此类数据结构，判断数据结构中是否存在，如果有直接从散列表中取值返回，不需要重复计算，这就避免了重复计算问题。具体代码如下:

let mapData = new Map()
function fib(n){
  if(n == 0 || n ==1) return 1;
  if(mapData.get(n)){
       return mapData.get(n);
   }
  let value = fib(n-1) + fib(n-2)
  mapData.set(n, value)
  return value
  
}

递归算法实战

1.实现深拷贝

function deepClone(target, map = new WeakMap()) {
   if (typeof target === 'object') {
       let cloneTarget = Array.isArray(target) ? [] : {};
       if (map.get(target)) {
           return map.get(target);
       }
       map.set(target, cloneTarget);
       for (const key in target) {
           if (target.hasOwnProperty(key)) {
               cloneTarget[key] = deepClone(target[key], map);
           }
       }
       return cloneTarget;
   } else {
       return target;
   }
}

2.数组扁平化

function flatten(arr) {
   let res = []
   arr.forEach((item, index) => {
       Array.isArray(item) ? res = res.concat(flatten(item)) : res.push(item)
   })
   return res
}

如上就实现了一个简单的数组扁平化的方法，现在我们拓展一下，能否实现其扁平化的深度呢，实现如下效果，举个🌰 flatten([1,[2,3,[4,5]]], 2) ---> [1,2,3,[4,5]]

function flatten(arr, depth = 0) {
   let res = []
   let d = 0
   ++d
   arr.forEach((item, index) => {
       (Array.isArray(item) && d <= depth) ? res = res.concat(flatten(item)) : res.push(item)
   })
   return res
}

3.使用递归实现`getElementsByClassName`

let arr = [];
   function byClass(node, className, arr){
       //得到传入节点的所有子节点
       var lists = node.childNodes;
       for(var i = 0;i< lists.length;i++){
           //判断是否有相同className元素
           if(arr[i],className == className){
               arr.push(arr[i]);
           }
           //判断子节点是否还有子节点
           if(arr[i].childNodes.length > 0){
               byClass(arr[i],className,arr);
           }
       }
   }

总结

其实递归被广泛的应用于各个地方，如前端er常用的Vue中Vnode的diff也是通过递归来实现的，以上就是我对递归思想的一个简单总结，2019最后一天，那就提前祝大家新的一年bug-free吧