【递归】数组和对象的相关递归

原创 老姚 随笔 递归,俺跟你拼了 848阅读 2017-05-11 12:57:56 举报

递归是函数调用自身,而函数又是可复用的代码封装。
那么递归必然每次都是进行相同的处理逻辑。
递归会使原先的大问题变小,变小后的问题还用“相同的逻辑”来处理。

说到“相同的逻辑”,不由得让人会想到数组和对象。
因为数组中的元素可以是数组,
对象中的属性值也可以是对象。
那么对嵌套的数组和嵌套的对象的遍历,必然需要使用递归。

1.遍历嵌套数组
javascript 代码

visit函数里面使用了Array#forEach方法,其中的return的作用只是让函数结束罢了。

如果我要找出嵌套数组中的所有偶数,可能需要如下调用:
javascript 代码

从上面可以看出visit还是有所局限。
可能你会想,此时visit如果不用forEach而是能用Array#filter之类API就好了。
其实,此时真正需求是:
如果能把嵌套数组“展平”变成一维数组,那岂不是想用什么API,就用什么了。

展平函数也需要使用递归:
javascript 代码

2.嵌套对象的遍历
对象的深拷贝就是其中应用之一。
它也需要使用递归,简单实现如下:
javascript 代码

jQuery中的拓展方法extend,总体上的实现原理也如此一般。

还有一种应用,对象的值相等比较操作。
javascript 代码

这是一个简单实现版本,详细的请参考underscore.js的isEqual实现。

上面就是数组和对象中常用的递归。
因为递归总需要让问题的规模逐渐减小,必然不能无限循环下去。
上面的代码都是简单实现,因为实现过程中并没有考虑循环引用的问题。
何为循环引用?对象属性引用对象本身。例如:
javascript 代码

首先,上面代码请拷到本地运行。
我们知道它在JS中并不会报错,而且也不会占用多大内存空间。
因为属性的值,仅仅是个引用罢了。
如果要考虑这种情形,上面的所有函数都要重新改写一遍。
此时需要维护一个引用栈,这里以数组展平函数为例:
javascript 代码

underscore.js中的isEqual方法,也是这么做的。

小结,本文总结了数组和对象相关的递归情景。
都不太难,读者如果自己实现一遍,估计就不再畏惧递归了。

本文完。

《递归系列目录》

看到此处我们该想到,陆游诗人对前端界做出的最大贡献:
纸上得来终觉浅,绝知此事要躬行。

评论 ( 7 )
最新评论
zzgbsh 6F 2017-05-12 09:33:58 7F

曉得了,

老姚 5F 2017-05-11 18:16:48 6F

不好意思,之前没明白你说的

老姚 4F 2017-05-11 17:54:41 5F

跟执行不执行没关系,写法有问题,你直接那么写会被解析成代码块。
改成({}).toString.call(1)就没问题。

zzgbsh 3F 2017-05-11 17:26:22 4F

我说的是直接执行,不是logjavascript 代码

老姚 2F 2017-05-11 14:28:32 3F

虽然没使用变量缓存,但是不会报错的javascript 代码

老姚 1F 2017-05-11 14:23:27 2F

你确定会报错?

zzgbsh 2017-05-11 14:16:39 1F

{}.toString.call(a)爲什麽不用變量緩存,執行會報錯