阅读 908

前端递归思想(禁止套娃)

什么是递归

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

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

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

举个🌰

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

关注下面的标签,发现更多相似文章
评论