JavaScript 中的一个例子
这是一个使用 JavaScript 的示例。目前，大多数浏览器不支持尾调用优化，因此以下代码段将失败
const repeat = n => f => x =>
n === 0 ? x : repeat (n - 1) (f) (f(x))
console.log(repeat(1e3) (x => x + 1) (0)) // 1000
console.log(repeat(1e5) (x => x + 1) (0)) // Error: Uncaught RangeError: Maximum call stack size exceeded
蹦床
我们可以通过改变我们写重复的方式来解决这个限制，但只是稍微改变一下。我们不会直接或立即返回一个值，而是返回我们的两种蹦床类型之一，Bounce或者Done. 然后我们将使用我们的trampoline函数来处理循环。
// 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
}
// our revised repeat function, now stack-safe
const repeat = n => f => x =>
n === 0 ? Done(x) : Bounce(repeat (n - 1) (f), f(x))
// apply trampoline to the result of an ordinary call repeat
let result = trampoline(repeat(1e6) (x => x + 1) (0))
// no more stack overflow
console.log(result) // 1000000
柯里化也会稍微减慢速度，但我们可以使用递归的辅助函数来弥补这一点。这也很好，因为它隐藏了蹦床的实现细节，并且不期望调用者反弹返回值。这运行速度大约是上面的两倍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
Trampolines 很好，但不得不担心调用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)) // 1000000
console.timeEnd ('loop/recur') // 24 ms
最初这种风格会让人感觉陌生，但随着时间的推移，我发现它在制作持久程序时是最一致的。下面的评论有助于您轻松了解表达式丰富的语法 -
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
)
)
延续单子
这是我最喜欢的主题之一，所以我们将看看延续 monad 是什么样子。重用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
}
// cont : 'a -> 'a cont
const cont = x =>
k => recur (k, x)
// chain : ('a -> 'b cont) -> 'a cont -> 'b cont
const chain = f => mx =>
k => recur (mx, x => recur (f (x), k))
// runCont : ('a -> 'b) -> a cont -> 'b
const runCont = f => mx =>
loop ((r = mx, k = f) => r (k))
const repeat = n => f => x =>
{ const aux = n => x =>
n === 0 // terminating condition
? cont (x) // base case, continue with x
: chain // otherise
(aux (n - 1)) // sequence next operation on
(cont (f (x))) // continuation of f(x)
return runCont // run continuation
(identity) // identity; pass-thru
(aux (n) (x)) // the continuation returned by aux
}
console.time ('cont monad')
console.log (repeat (1e6) (x => x + 1) (0)) // 1000000
console.timeEnd ('cont monad') // 451 ms
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
}
// stack-safe Y combinator
const Y = f => {
const safeY = f =>
bounce((...xs) => f (safeY (f), ...xs))
return (...xs) =>
trampoline (safeY (f) (...xs))
}
// recur safely to your heart's content
const repeat = Y ((recur, n, f, x) =>
n === 0
? x
: recur (n - 1, f, f (x)))
console.log(repeat (1e5, x => x + 1, 0)) // 10000
while循环的实用性
但老实说：当我们忽略一个更明显的潜在解决方案时，这是很多仪式：使用fororwhile循环，但将其隐藏在功能接口后面
出于所有意图和目的，此repeat函数的工作方式与上面提供的函数相同 - 除了此函数快一到两亿倍（loop/recur解决方案除外）。oop，它也可以说更容易阅读。
诚然，这个函数可能是一个人为的例子——并非所有的递归函数都可以如此轻松地转换为fororwhile循环，但在这种可能的情况下，最好这样做。当一个简单的循环不起作用时，保存蹦床和继续进行繁重的工作。
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) // 100000000
setTimeout 不是堆栈溢出问题的解决方案
好的，所以它确实有效，但只是自相矛盾。如果您的数据集很小，则不需要，setTimeout因为不会有堆栈溢出。如果您的数据集很大并且您将其setTimeout用作安全的递归机制，那么您不仅无法从您的函数中同步返回一个值，而且速度会非常慢，您甚至不想使用您的函数
有些人发现一个面试问答准备网站鼓励这种可怕的策略
我们repeat将使用的样子setTimeout——注意它也是在延续传递风格中定义的——即，我们必须repeat使用回调 ( k)调用以获得最终值
// do NOT implement recursion using setTimeout
const repeat = n => f => x => k =>
n === 0
? k (x)
: setTimeout (x => repeat (n - 1) (f) (x) (k), 0, f (x))
// be patient, this one takes about 5 seconds, even for just 1000 recursions
repeat (1e3) (x => x + 1) (0) (console.log)
// comment the next line out for absolute madness
// 10,000 recursions will take ~1 MINUTE to complete
// paradoxically, direct recursion can compute this in a few milliseconds
// setTimeout is NOT a fix for the problem
// -----------------------------------------------------------------------------
// repeat (1e4) (x => x + 1) (0) (console.log)
这有多糟糕，我再怎么强调也不为过。甚至1e5需要很长时间才能运行，以至于我放弃了对其进行测量的尝试。我没有将其包含在下面的基准测试中，因为它太慢而无法被视为可行的方法。
Promise
Promise 具有链接计算的能力并且是堆栈安全的。然而，repeat使用 Promises实现堆栈安全意味着我们必须放弃我们的同步返回值，就像我们使用setTimeout. 我将其作为“解决方案”提供，因为它确实解决了问题，不像setTimeout，但与蹦床或延续 monad 相比，它的方式非常简单。正如您可能想象的那样，性能有些糟糕，但远不及setTimeout上面的示例那么糟糕
在这个解决方案中值得注意的是，Promise 的实现细节对调用者是完全隐藏的。单个延续作为第四个参数提供，并在计算完成时调用。
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))
// be patient ...
repeat (1e6) (x => x + 1) (0) (x => console.log('done', x))
基准
严重的是，while环是很多快-几乎一样快100倍（进行比较时，最好到最差-但不包括异步答案：setTimeout和Promise）
// sync
// -----------------------------------------------------------------------------
// repeat implemented with basic trampoline
console.time('A')
console.log(tramprepeat(1e6) (x => x + 1) (0))
console.timeEnd('A')
// 1000000
// A 114 ms
// repeat implemented with basic trampoline and aux helper
console.time('B')
console.log(auxrepeat(1e6) (x => x + 1) (0))
console.timeEnd('B')
// 1000000
// B 64 ms
// repeat implemented with cont monad
console.time('C')
console.log(contrepeat(1e6) (x => x + 1) (0))
console.timeEnd('C')
// 1000000
// C 33 ms
// repeat implemented with Y
console.time('Y')
console.log(yrepeat(1e6) (x => x + 1) (0))
console.timeEnd('Y')
// 1000000
// Y 544 ms
// repeat implemented with while loop
console.time('D')
console.log(whilerepeat(1e6) (x => x + 1) (0))
console.timeEnd('D')
// 1000000
// D 4 ms
// async
// -----------------------------------------------------------------------------
// repeat implemented with Promise
console.time('E')
promiserepeat(1e6) (x => x + 1) (0) (console.log)
console.timeEnd('E')
// 1000000
// E 2224 ms
// repeat implemented with setTimeout; FAILED
console.time('F')
timeoutrepeat(1e6) (x => x + 1) (0) (console.log)
console.timeEnd('F')
// ...
// too slow; didn't finish after 3 minutes
石器时代 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');
// 100000
// JS1 100K: 15ms
console.time('JS1 100M');
console.log (repeat (1e8, function (x) { return x + 1 }, 0));
console.timeEnd('JS1 100M');
// 100000000
// JS1 100K: 5999ms
使用石器时代 JavaScript 的非阻塞无限递归
如果出于某种原因，您想要非阻塞（异步）无限递归，我们可以依靠在计算开始时setTimeout延迟单个帧。该程序还使用了石器时代的 javascript 并在 8 秒内计算了 100,000,000 次递归，但这次以非阻塞方式进行。
这表明具有非阻塞要求没有什么特别之处。一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) {
// setTimeout is called ONCE at the start of the computation
// NOT once per recursion
return setTimeout(function () {
while (t && t.isBounce) {
t = t.f (t.x);
}
return t.k (t.x);
}, 0);
}
// stack-safe infinite recursion, non-blocking, 100,000,000 recursions in under 8 seconds
// now repeatk expects a 4th-argument callback which is called with the asynchronously computed result
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')
// non-blocking line 1
// non-blocking line 2
// [ synchronous program stops here ]
// [ below this line, asynchronous program continues ]
// non-blocking line 3 100000000
// non-blocking JS1: 7762ms