JavaScript示例
以下是使用JavaScript的示例。目前，大多数浏览器不支持尾调用优化，因此以下代码段将失败。
const repeat = n => f => x =>
n === 0 ? x : repeat (n - 1) (f) (f(x))
console.log(repeat(1e3) (x => x + 1) (0))
console.log(repeat(1e5) (x => x + 1) (0))
弹跳（Trampolines）
我们可以通过改变 repeat 函数的写法来解决这个限制，但只需稍作修改。我们不再直接返回一个值或者立即递归调用，而是返回两种 trampoline 类型之一：Bounce 或 Done。然后我们将使用 trampoline 函数来处理循环。
const Bounce = (f,x) => ({ isBounce: true, f, x })
const Done = x => ({ isBounce: false, x })
const trampoline = ({ isBounce, f, x }) => {
while (isBounce)
({ isBounce, f, x } = f(x))
return x
}
const repeat = n => f => x =>
n === 0 ? Done(x) : Bounce(repeat (n - 1) (f), f(x))
let result = trampoline(repeat(1e6) (x => x + 1) (0))
console.log(result)
柯里化也会稍微降低速度，但我们可以使用一个辅助函数来解决递归问题。这也很好，因为它隐藏了跳板实现细节，不需要调用者弹回返回值。与上面的repeat相比，这运行速度大约快两倍。
// aux helper hides trampoline implementation detail
// runs about 2x as fast
const repeat = n => f => x => {
const aux = (n, x) =>
n === 0 ? Done(x) : Bounce(x => aux (n - 1, x), f (x))
return trampoline (aux (n, x))
}
Clojure风格的loop/recur
跳板很好，但必须担心在函数返回值上调用trampoline有些烦人。我们看到的替代方法是使用辅助帮助器，但这也有点烦人。我确定你们中的一些人对Bounce和Done包装器也不太感兴趣。
Clojure创建了一个专门的跳板接口，使用一对函数loop和recur - 这个配对组合非常优雅地表达了程序。
哦，它也非常快。
const recur = (...values) =>
({ recur, values })
const loop = run =>
{ let r = run ()
while (r && r.recur === recur)
r = run (...r.values)
return r
}
const repeat = n => f => x =>
loop
( (m = n, r = x) =>
m === 0
? r
: recur (m - 1, f (r))
)
console.time ('loop/recur')
console.log (repeat (1e6) (x => x + 1) (0))
console.timeEnd ('loop/recur')
起初，这种风格可能会感到陌生，但随着时间的推移，我发现它在制作耐久程序时是最一致的。下面的注释有助于使您逐步适应富表达式语法 -
const repeat = n => f => x =>
loop // begin a loop with
( ( m = n // local loop var m: counter, init with n
, r = x // local loop var r: result, init with x
) =>
m === 0 // terminating condition
? r // return result
: recur // otherwise recur with
( m - 1 // next m value
, f (r) // next r value
)
)
续延单子
这是我最喜欢的主题之一，因此我们将看看使用续延单子实现的情况。通过重用loop和recur，我们实现了一个堆栈安全的cont，它可以使用chain序列化操作并使用runCont运行操作序列。对于repeat来说，这是毫无意义的（而且速度很慢），但在这个简单的例子中，看到cont的机制工作仍然很酷。
const identity = x =>
x
const recur = (...values) =>
({ recur, values })
const loop = run =>
{ let r = run ()
while (r && r.recur === recur)
r = run (...r.values)
return r
}
const cont = x =>
k => recur (k, x)
const chain = f => mx =>
k => recur (mx, x => recur (f (x), k))
const runCont = f => mx =>
loop ((r = mx, k = f) => r (k))
const repeat = n => f => x =>
{ const aux = n => x =>
n === 0
? cont (x)
: chain
(aux (n - 1))
(cont (f (x)))
return runCont
(identity)
(aux (n) (x))
}
console.time ('cont monad')
console.log (repeat (1e6) (x => x + 1) (0))
console.timeEnd ('cont monad')
Y组合子
Y组合子是我灵感的来源;如果不把它与其他技术放在一起，这个答案就不完整了。然而，大多数Y组合子的实现都不是堆栈安全的，如果用户提供的函数递归次数太多，就会溢出。由于这个答案关注保持堆栈安全行为，所以当然我们会以安全的方式实现Y - 再次依靠我们可靠的跳板。
Y演示了扩展易于使用、堆栈安全、同步无限递归的能力，而不会使您的函数混乱不堪。
const bounce = f => (...xs) =>
({ isBounce: true, f, xs })
const trampoline = t => {
while (t && t.isBounce)
t = t.f(...t.xs)
return t
}
const Y = f => {
const safeY = f =>
bounce((...xs) => f (safeY (f), ...xs))
return (...xs) =>
trampoline (safeY (f) (...xs))
}
const repeat = Y ((recur, n, f, x) =>
n === 0
? x
: recur (n - 1, f, f (x)))
console.log(repeat (1e5, x => x + 1, 0))
使用while循环的实用性
但是说实话：当我们忽略了更明显的潜在解决方案时，这就是很多仪式。可以使用for或while循环，但将其隐藏在函数接口后面。
就所有目的而言，这个repeat函数的工作方式与上面提供的函数完全相同 - 除了这个函数可能快一两亿倍（除了loop/recur解决方案）。它甚至可能更容易阅读。
当然，这个函数可能是一个牵强的例子 - 并非所有递归函数都可以如此轻松地转换为for或while循环，但在这种情况下，最好就像这样做。当简单的循环不起作用时，请将跳板和连续性保留给重型升降机。
const repeat = n => f => x => {
let m = n
while (true) {
if (m === 0)
return x
else
(m = m - 1, x = f (x))
}
}
const gadzillionTimes = repeat(1e8)
const add1 = x => x + 1
const result = gadzillionTimes (add1) (0)
console.log(result)
setTimeout不是解决堆栈溢出问题的方法
好吧，它确实可以工作，但只是矛盾的。如果您的数据集很小，您不需要setTimeout，因为不会发生堆栈溢出。如果您的数据集很大并且使用setTimeout作为安全递归机制，不仅无法同步从函数返回值，而且速度非常慢，您甚至都不想使用函数
有些人发现了一个面试Q&A准备网站，鼓励这种可怕的策略
使用setTimeout重复的样子 - 请注意，它也以延续传递样式定义 - 即，我们必须使用回调(k)调用repeat才能获得最终值
const repeat = n => f => x => k =>
n === 0
? k (x)
: setTimeout (x => repeat (n - 1) (f) (x) (k), 0, f (x))
repeat (1e3) (x => x + 1) (0) (console.log)
我无法强调这有多糟糕。即使是
1e5，运行时间也太长了，以至于我放弃尝试测量它。我不会在下面的基准测试中包含它，因为它太慢了，甚至不能被视为一种可行的方法。
承诺（Promises）
承诺具有链接计算和堆栈安全的能力。然而，使用 Promises 来实现一个堆栈安全的 repeat 意味着我们将不得不放弃同步返回值，就像我们使用 setTimeout 一样。我提供这个"解决方案"是因为它确实解决了问题，不像 setTimeout 那样，但与 trampoline 或 continuation monad 相比，它非常简单。尽管性能有些差，但远不及上面的 setTimeout 示例那么糟糕。
需要注意的是，这个解决方案中，Promise 的实现细节对调用者完全隐藏。一个单一的 continuation 作为第四个参数提供，并且在计算完成时被调用。
const repeat = n => f => x => k =>
n === 0
? Promise.resolve(x).then(k)
: Promise.resolve(f(x)).then(x => repeat (n - 1) (f) (x) (k))
repeat (1e6) (x => x + 1) (0) (x => console.log('done', x))
基准测试
说真的，while 循环要快得多 - 像是快了将近100倍（比较最好和最差情况，但不包括异步回答：setTimeout 和 Promise）。
console.time('A')
console.log(tramprepeat(1e6) (x => x + 1) (0))
console.timeEnd('A')
console.time('B')
console.log(auxrepeat(1e6) (x => x + 1) (0))
console.timeEnd('B')
console.time('C')
console.log(contrepeat(1e6) (x => x + 1) (0))
console.timeEnd('C')
console.time('Y')
console.log(yrepeat(1e6) (x => x + 1) (0))
console.timeEnd('Y')
console.time('D')
console.log(whilerepeat(1e6) (x => x + 1) (0))
console.timeEnd('D')
console.time('E')
promiserepeat(1e6) (x => x + 1) (0) (console.log)
console.timeEnd('E')
console.time('F')
timeoutrepeat(1e6) (x => x + 1) (0) (console.log)
console.timeEnd('F')
JavaScript的石器时代
以上技术是使用更新的ES6语法演示的，但您可以在最早版本的JavaScript中实现一个跳板，它只需要while和一等函数。
以下内容使用JavaScript的石器时代演示了无限递归是可能的，并且在不必牺牲同步返回值的情况下性能良好 - 在 6 秒内实现 100,000,000 次递归 - 与 只能在相同时间内 1,000 次递归的setTimeout相比，这是一个巨大的差异。
function trampoline (t) {
while (t && t.isBounce)
t = t.f (t.x);
return t.x;
}
function bounce (f, x) {
return { isBounce: true, f: f, x: x };
}
function done (x) {
return { isBounce: false, x: x };
}
function repeat (n, f, x) {
function aux (n, x) {
if (n === 0)
return done (x);
else
return bounce (function (x) { return aux (n - 1, x); }, f (x));
}
return trampoline (aux (n, x));
}
console.time('JS1 100K');
console.log (repeat (1e5, function (x) { return x + 1 }, 0));
console.timeEnd('JS1 100K');
console.time('JS1 100M');
console.log (repeat (1e8, function (x) { return x + 1 }, 0));
console.timeEnd('JS1 100M');
使用史前JavaScript实现非阻塞无限递归
如果出于某种原因，您需要非阻塞（异步）无限递归，我们可以依靠
setTimeout在计算开始时延迟一个
单帧。该程序还使用史前javascript，在不阻塞的情况下计算了100,000,000次递归，但这次只用了不到8秒。
这说明，具有非阻塞要求并没有什么特别之处。一个
while循环和一级函数仍然是实现堆栈安全递归而不牺牲性能的唯一基本要求。
在现代程序中，鉴于Promises，我们将把
setTimeout调用替换为单个Promise。
function donek (k, x) {
return { isBounce: false, k: k, x: x };
}
function bouncek (f, x) {
return { isBounce: true, f: f, x: x };
}
function trampolinek (t) {
return setTimeout(function () {
while (t && t.isBounce) {
t = t.f (t.x);
}
return t.k (t.x);
}, 0);
}
function repeatk (n, f, x, k) {
function aux (n, x) {
if (n === 0)
return donek (k, x);
else
return bouncek (function (x) { return aux (n - 1, x); }, f (x));
}
return trampolinek (aux (n, x));
}
console.log('non-blocking line 1')
console.time('non-blocking JS1')
repeatk (1e8, function (x) { return x + 1; }, 0, function (result) {
console.log('non-blocking line 3', result)
console.timeEnd('non-blocking JS1')
})
console.log('non-blocking line 2')
