递归优化
递归在我们平时撸码中会经常用到, 不过可能很多人不知道递归的弊端, 就是会导致调用栈越来越深. 如果没有节制的使用递归可能会导致调用栈溢出.
那什么是递归呢?
递归调用是一种特殊的嵌套调用, 是某个函数调用自己或者是调用其他函数后再次调用自己的, 只要函数之间互相调用能产生循环的则一定是递归调用, 递归调用一种解决方案, 一种是逻辑思想, 将一个大工作分为逐渐减小的小工作, 比如说一个和尚要搬 50 块石头, 他想, 只要先搬走 49 块, 那剩下的一块就能搬完了, 然后考虑那 49 块, 只要先搬走 48 块, 那剩下的一块就能搬完了, 递归是一种思想, 只不过在程序中, 就是依靠函数嵌套这个特性来实现了.
那什么又是调用栈呢?
下面的是我写的一个简单的递归调用, 通过断点我们可以看到每执行一个 test 函数, 调用栈就会多一个 test 函数.
当我们执行到 i=0 的时候, 这个时候调用栈是最深的有 11 个 test 函数, 之后又会逐个移除 test 函数, 可以看图二的动图, 可以看出调用栈是先进后出的
- function test (i) {
- if (i <0) return
- test(--i)
- }
- // 这个会调用自身 11 次
- test(10)
图 1:
图 2:
那怎么对递归进行优化呢, 既能起到递归的作用又不会加深调用栈
这里会用到 while 循环的思想, 调用栈之所以会加深主要是因为方法内调用方法, 必须等待方法执行完成这个任务才算是真正的结束, 就像 A 同学有个任务 1, 这个任务是让 B 同学完成任务 2, 在 B 同学没有完成之前, A 同学一直处理工作状态.
那 while 循环是什么原理呢, 可以理解为将有调用关系的方法平铺为同一级别. 这需要引入额外的方法来做调度, 本来 test 方法需要调用自己 10 次的, 现在用方法 b 通过标记的方法来决定是否需要调用 test 方法
下面的的例子就是实现递归优化的实现方法 (这里复制于阮一峰的 es6 教程)
这是一个很巧妙的方法, 我说下它的实现步骤:
利用闭包将 f 方法保留 (这里的 f 方法就是我们需要递归调用的方法)
创建 value,active,accumulated 三个变量, 并利用了闭包原理避免被垃圾回收
accumulated 是保存每次 f 方法调用后需要传入 f 的新的形参, active 是标记 f 方法是否执行到了最后一次循环, value 是记录需要返回的值
下面的因为 tco 会 return 一个新的函数 accumulator, 所以 sum=accumulator, 然后再 accumulator 内只要 accumulated 长度不为 0,while 就会一直执行, 每次执行 sum 方法就会 accumulated.push(arguments) 方法, 这样 accumulated 长度就不会为 0. 所以只要 f.apply(this, accumulated.shift()) 执行的时候一旦不调用 sum(x + 1, y - 1) 方法, accumulated 就不会有 push 操作, 这时 while 就会停止. 然后就是 active, 我们看到 if (!active) {...} 这个操作, 这里保证了只有第一次调用 accumulator 方法时会进入 while 循环, 剩下的只是起到 accumulated.push(arguments) 的作用. 直到 while 循环停止, return 出来的就是经过 n 次调用 f 方法后返回的值了.
这样就可以把一个递归调用转换为 while 循环实现了
- function tco(f) {
- var value;
- var active = false;
- var accumulated = [];
- return function accumulator() {
- // 这里 accumulated 将形参入栈
- accumulated.push(arguments);
- // 这里保证只有第一次调用才会进入
- if (!active) {
- active = true;
- while (accumulated.length) {
- value = f.apply(this, accumulated.shift());
- }
- active = false;
- return value;
- }
- };
- }
- var sum = tco(function(x, y) {
- if (y> 0) {
- return sum(x + 1, y - 1)
- }
- else {
- return x
- }
- });
- sum(1, 100000)
这里可能会有点难理解, 可以多试几次, 打断点看看控制台的调用栈. 相信还是可以看出其中的原理的
来源: https://www.cnblogs.com/suyuanli/p/12008109.html