生成器是现代语言中一种非常强大的特性，它的应用场景非常多，如惰性求值、无限流、协程等。
本文以JavaScript为示例介绍如何使用生成器将任意递归函数转换为非递归运行，避免栈溢出风险，同时在转换过程中仍然保持递归算法的可读性。
JavaScript生成器简介
在JavaScript中可以使用function*定义生成器函数。与普通函数不同，调用生成器函数返回的是一个生成器对象。生成器本质上是一个迭代器，完全兼容迭代器的接口。
function* generator(n) {
for (let i = 1; i <= n; i++) {
yield i
}
return 'done'
}
let g = generator(3)
console.log(g.next()) // {value: 1, done: false}
console.log(g.next()) // {value: 2, done: false}
console.log(g.next()) // {value: 3, done: false}
console.log(g.next()) // {value: 'done', done: true}
在生成器函数内部，可以使用
yield关键字产生值。yield会暂停生成器函数的执行，并产生一个值。生成器函数内部也可以包含
return语句，return会结束整个生成器，并将返回值作为最后产生的值。调用生成器的
next方法可以从头启动生成器，或者从上一条yield语句恢复执行，直到遇到下一条yield表达式。next方法的返回值是一个迭代器对象，包含value和done字段，分别表示当前产生的值和是否结束。
调用生成器的next方法时可以传递参数，这个值作为yield表达式返回的值：
function* generator() {
let n = yield 123
yield n + 1
}
let g = generator()
console.log(g.next()) // {value: 123, done: false}
console.log(g.next(456)) // {value: 457, done: false}
将递归函数改写为生成器函数
将普通递归函数做一点小改动，即可转换为生成器函数：
- 将函数声明
function为function* - 使用
yield表达式替换所有递归调用的地方
下面是一个例子：
// 普通递归函数求1+2+3+...+n
function sum(n) {
if (n == 1) {
return 1
}
return n + sum(n - 1)
}
// 改写成生成器函数的递归函数
function* sum(n) {
if (n == 1) {
return 1
}
return n + (yield sum(n - 1))
}
运行递归函数的生成器
经过以上的改写，sum函数变成了一个生成器函数，这个生成器函数还不能直接运行，需要一个“发动机”驱动整个生成器函数不断运行：
/**
* 运行递归函数生成器
* @param {*} g 生成器
* @returns 返回值
*/
function runGenerator(g) {
let stack = [g] // 调用栈
let ret = null // 保存当前返回值
while (stack.length > 0) {
let cur = stack[stack.length - 1] // 获取栈顶元素
let r = cur.next(ret) // 运行当前生成器
if (r.done) { // 如果生成器已结束，则记录返回值
ret = r.value
stack.pop()
} else { // 否则查看生成器返回的值类型
if (isGenerator(r.value)) { // 如果产生的是另一个生成器，则直接入栈
stack.push(r.value)
} else { // 如果产生的是一个普通值，则记录返回值
ret = r.value
}
}
}
return ret
}
以上runGenerator就是生成器函数的驱动器。如果我们将生成器视为栈帧，将yield语句视作函数调用，将生成器执行结束当作函数返回，则runGenerator的逻辑就是用栈模拟函数调用的操作。整个过程没有任何递归的操作，因此也不存在栈溢出的问题。
下面使用runGenerator运行递归函数生成器：
console.log(runGenerator(sum(100))) // 5050
console.log(runGenerator(sum(1000000))) // 500000500000，无栈溢出
总结
使用上面介绍的技巧可以将任意递归函数以非递归的方式执行，避免栈溢出的风险，同时保持原始递归函数的基本结构和可读性。另外，这个技巧不仅适用于JavaScript，同时还适用于任意支持生成器（yield）特性的编程语言。
完整代码和更多示例参见：