Javascript 如何给一个深度递归（使用了setTimeout）设置完成后回调？

推荐关注

› Meteor

› JSLint - a JavaScript code quality tool

› jsFiddle

› D3.js

› WebStorm

推荐书目

› JavaScript 权威指南第 5 版

› Closure: The Definitive Guide

This topic created in 4975 days ago, the information mentioned may be changed or developed.

因为递归太深而使用了异步的 setTimeout 清空调用栈，整个递归变成了异步的行为，怎么设置完成后的回调？

简单的代码示例：

var stackSize = 0;

function foo(a){
stackSize ++;

bar();

if (!a.length) return;

if (stackSize > 1000) {
stackSize = 0;
setTimeout(function(){
a.forEach(foo);
},0);
} else {
a.forEach(foo);
}
}

foo(hugeArray); //hugeArray 是一个多层嵌套的数组, 像这样 [[[...],[...]],[...]]

stackSize

foo

setTimeout

14 replies • 1970-01-01 08:00:00 +08:00

yulanggong

Sep 28, 2012

怎么不能编辑了？

这是上面的代码
<script src="https://gist.github.com/3798444.js"> </script>

yulanggong

Sep 28, 2012

https://gist.github.com/3798444

yulanggong

Sep 28, 2012

真崩溃
http://gist.github.com/3798444

haohaolee

Sep 28, 2012

一个疑问，stackSize 真的能反映当前递归的深度吗？出函数的时候是不是要 stackSize-- 一下啊？
另外，为什么要选择这么难以理解的解决方式呢，如果不是非要使用递归的话，可以用一个数据结构模拟栈或者别的神马嘛，比如树的遍历

skyleft

Sep 28, 2012

使用全局变量

yulanggong

Sep 28, 2012

@haohaolee
stackSize 的确是错的，因为 forEach 那会进入不同的分支。可以改为 stackSize 作为参数传给递归的函数用来分别统计。
你能说说用数据结构模拟栈的思路吗？我没什么编程基础。

chone

Sep 28, 2012

callback是不是要在所有遍历完成后调用，那样需要能逐级向上反馈完成的信号吧，这样在子级遍及没有完成前，父级需要被阻塞以等待信号。阻塞的实现好像也要用settimeout,父级和子级之间的通讯可以使用forEach的bind参数。

不过这样的处理又复杂，效率又差。@haohaolee 说的比较靠谱。

yulanggong

Sep 28, 2012

@chone
我搜了下非递归遍历，发现这可能是 @haohaolee 说得方式，我在琢磨怎么写代码。

逐级汇报是一个思路，不过我还想不出怎么实现。

我原来有个思路是在递归的函数里累加一个全局变量，然后定时轮询这个变量，变量在一段时间内没有变化时就是递归完成了，只是这样回调不太及时。

haohaolee

Sep 28, 2012

@yulanggong 我觉得你可以参考树遍历的方式，应该有很多资料。
提供一个思路，设想有一个队列 q (javascript原生是否支持队列我不知道)
1. 把a数组放进队列 2 若队列不为空循环处理队列: 取出队列头的元素，遍历该数组，若元素仍为数组则加入队列尾，若为非数组则直接处理

skyleft

Sep 28, 2012

使用栈实现递归，类似树的非递归遍历，但是树的节点之间有指针链接，这里用两个栈。

初始化两个栈S1，S2（js无，自己实现），s1存下标，s2存数组
s1.push(0)
s2.push(arr)
while(s not empty){
i=s1.pop();arri=s2.pop();
循环arri,如果是元素，就访问它,如果还是数组，就将其在父数组中的下标压入栈S1，将父数组压入栈S2
}

shawiz

Sep 28, 2012

non-blocking 的 callback 可以用 jquery 的 deferred 来解决。
比如:

<script src="https://gist.github.com/3798898.js"> </script>

shawiz

Sep 28, 2012

http://gist.github.com/3798898

haohaolee

Sep 28, 2012

@shawiz 没看懂这个例子，这个例子能做到所有的foo都结束的时候回调吗

shawiz

Sep 29, 2012

@haohaolee 豆瓣上别人推荐了一篇关于 Javascript 异步的文章，值得一读，也许能解决你的疑问。我介绍的是 promise 方法。

http://jimliu.net/?p=12