js一个神奇的尾递归优化

原文链接: js 一个神奇的尾递归优化

上一篇: 编程类最强字体 FiraCode

下一篇: 一个去中心化的免费电子书共享网站 JS解码URL和编码URL

参考

https://www.zhihu.com/question/414097020/answer/1442510541

测试代码

const getList = (size) => Array(size).fill(1);const sum = (list) => {if (list.length === 1) return list[0];const prev = list.pop();return prev + sum(list);
};const sumAsync = async (list) => {await undefined;if (list.length === 1) return list[0];const prev = list.pop();return prev + (await sumAsync(list));
};console.log(getList(10));
sumAsync(getList(10)).then(console.log);
console.log(sum(getList(10)));async function test(size) {sumAsync(getList(size)).then((data) => {console.log("async", data);console.log(sum(getList(size)));});
}
test(20000);


异步的可以正常执行, 但是同步的会爆栈

同步代码, 栈空间是O(n) 的, 在列表比较大的情况下会直接把栈内存占满后报错

异步代码, 首先直觉上也是O(n)的, 但是确实可以成功输出

作者的说法, 即async将栈内存转移到堆中, 由于堆内存比栈大得多, 所以即使是小数据的O(n), 堆内存也是可以撑住的

左边是同步的, 执行是一样的 , 右边会变化, 也就是说转到了堆上

两个的区别只是注释了那个优化一行导致的

const async_hooks = require("async_hooks")let index = 0
let print_buffer = ""/*** async hooks会追踪async调用,* 而console.log使用异步输出,* 所以这里使用同步方法模拟console*/
function println(log) {print_buffer += log + "\n"
}/* 创建钩子 */
async_hooks.createHook({init(asyncId, type, triggerAsyncId) {const eid = async_hooks.executionAsyncId()println("init: *********************************")println("init: triggerAsyncId " + triggerAsyncId)println("init: executionAsyncId " + eid)println("init: asyncId " + asyncId)println("init: type " + type)}
})
.enable()/*********** 测试区 **********/
async function A() {/* 为了观察方便只执行2次 */println("A: runing")index += 1if (index === 2) return undefined// 有优化递归// await undefinedreturn await A()
}
/*********** 测试区 **********/A().then(() => {console.log(print_buffer)
})