ES6 递归、尾递归及优化学习

原创 蒋敬敏 随笔 ECMAScript 6 295阅读 2018-03-16 18:26:37 举报

递归函数的改写

函数式编程有一个概念,叫做柯里化(currying),意思是将多参数的函数转换成单参数的形式

上面代码通过柯里化,将尾递归函数tailFactorial变为只接受一个参数的factorial。

第二种方法就简单多了,就是采用 ES6 的函数默认值。

尾递归优化的实现

正常递归调用:

上面代码中,sum是一个递归函数,参数x是需要累加的值,参数y控制递归次数。一旦指定sum递归 100000 次,就会报错,提示超出调用栈的最大次数。

蹦床函数(trampoline)可以将递归执行转为循环执行。

上面就是蹦床函数的一个实现,它接受一个函数f作为参数。只要f执行后返回一个函数,就继续执行。注意,这里是返回一个函数,然后执行该函数,而不是函数里面调用函数,这样就避免了递归执行,从而就消除了调用栈过大的问题。

然后,要做的就是将原来的递归函数,改写为每一步返回另一个函数。

附注:

那么过多的递归调用为什么会引起栈溢出呢?事实上,函数调用的参数是通过栈空间来传递的,在调用过程中会占用线程的栈资源。而递归调用,只有走到最后的结束点后函数才能依次退出,而未到达最后的结束点之前,占用的栈空间一直没有释放,如果递归调用次数过多,就可能导致占用的栈资源超过线程的最大值,从而导致栈溢出,导致程序的异常退出。

测试JavaScript引擎能进行多少次递归调用

Aleph先生指出,在V8中,递归调用的数量取决于两个量:堆栈的大小和堆栈帧(保存参数的局部变量)的大小。你可以通过在 computeMaxCallStackSize() 添加局部变量进行验证 - 它会返回低位值。

欢迎前端爱好者加入QQ群:112916679 答疑解惑,且可获取更多最前沿的前端资料!

评论 ( 0 )
最新评论
暂无评论

赶紧努力消灭 0 回复