通常可以在使用JavaScript中的手动堆栈的函数中转换递归函数吗？

Question

注意以下功能：

function count(n) {
  if (n === 0) {
    return 0;
  } else {
    return 1 + count(n - 1);
  }
}

这是从0到N的最简单的递归函数。由于JavaScript的堆栈限制很小，因此该函数很容易溢出。通常，任何递归函数都可以使用手动堆栈转换为一个递归函数，因此不会出现堆栈溢出；但是这样做很复杂。在一般情况下，是否可以在不使用连续传递样式的情况下，使用自己的堆栈将JavaScript递归函数转换为？换句话说，假设我们写了：

const count = no_overflow(function(count) {
  return function(n) {
    if (n === 0) {
      return 0;
    } else {
      return 1 + count(n - 1);
    }
  }
});

是否有可能以这种新的no_overflow函数等效于旧函数的方式实现count，除非没有堆栈溢出？

注意：

1. 这是关于尾部调用优化的[[not，因为no_overflow应该适用于非尾递归函数。

2. Trampolining是

   not

有用的，因为在一般情况下，它要求函数以连续传递样式编写，而实际上不是。
3. 使用yield编写函数也不起作用，原因类似：您不能从内部lambda取得yield。
4. no_overflow本质上将像无栈的Y组合器一样工作。

Answer 1

在JavaScript中，调用函数f(x, y, ...)使我们受到堆栈和框架的基础实现细节的约束。如果重复使用函数应用程序，则会

绝对，不可避免地遇到堆栈溢出。

但是，如果我们可以采用稍微不同的表示法，例如call(f, x, y, ...)，则可以控制函数应用程序，但是我们需要-

const count = (n = 0) =>
  n === 0
    ? 0
    : call
        ( result => 1 + result
        , call(count, n - 1)     // <-- non tail
        )

console.log(noOverflow(count(99999)))
// 99999

实现noOverflow是在loop中定义的this Q&A的包装，>
const noOverflow = t =>
  loop(_ => t)
不足为奇的是，这是一个不平凡的问题，但是，如果您选择实施自己的解决方案，那么那里的答案应该有助于详细说明您必须考虑的事项和一些良好的测试用例。
展开下面的代码片段，以在浏览器中验证结果-
 
const call = (f, ...values) =>
  ({ type: call, f, values })

const recur = (...values) =>
  ({ type: recur, values })

const identity = x =>
  x

const loop = (f) =>
{ const aux1 = (expr = {}, k = identity) =>
    expr.type === recur
      ? call (aux, expr.values, values => call (aux1, f (...values), k))
  : expr.type === call
      ? call (aux, expr.values, values => call (aux1, expr.f (...values), k))
  : call (k, expr)

  const aux = (exprs = [], k) =>
    call
      ( exprs.reduce
          ( (mr, e) =>
              k => call (mr, r => call (aux1, e, x => call (k, [ ...r, x ])))
          , k => call (k, [])
          )
      , k
      )

  return run (aux1 (f ()))
}

const run = r =>
{ while (r && r.type === call)
    r = r.f (...r.values)
  return r
}

const noOverflow = t =>
  loop(_ => t)

const count = (n = 0) =>
  n === 0
    ? 0
    : call
        ( result => 1 + result
        , call(count, n - 1)     // <-- non tail
        )

console.log(noOverflow(count(99999)))
// 99999