你能做一个递归，记忆斐波那契函数使用js生成器?

Question

我发现的最优雅的斐波那契函数甚至不是递归的:

async function* fib(x) {
  let x1 = 0;
  let x2 = 1;
  let i = 0;
  while (i < x) {
    [x1, x2] = [x2, x1 + x2];
    i += 1;
  }
  yield x1;
}

生成器很棒。也就是说，它们也适合递归任务，因为你可以"懒惰地"执行它们。

传统上，斐波那契函数是递归或记忆的教科书范例。

到目前为止我想出的方法都不起作用。

所以我想知道:如何在JavaScript中实现递归的、记忆的斐波那契生成函数?

Answer 1

一些初步评论:

• async与yield无关。所以删除async在这里。
• 对于生成器，应该不需要传递指示序列结束的参数(x)。这应该是调用者施加的限制，生成器不应该担心。从生成器的角度来看，只要调用者从中提取值，它就应该无限制地继续运行。
• 递归版本无论如何必须在其他版本之前产生第一个斐波那契值，因此应用看起来像尾递归的模式是有意义的。这不需要记忆(除了传递两个连续的斐波那契值):

function* genFib (a=0, b=1) {
    yield a;
    yield *genFib(b, a+b);
}
let limit = 50;
for (let n of genFib()) {
    if (n > limit) break;
    console.log(n);
}

Answer 2

Trincot的回答很好地涵盖了你问题的递归生成器方面，我同意他们在这种情况下的评估方法:记忆。因为看起来你想要返回一个特定的斐波那契数，你可以简单地记住你在问题中发布的函数(减去async，因为这里不需要)。请记住，因为它只产生一次，所以它可以很容易地成为一个标准函数，因为无论您访问next()(并且只有)元素，都将支付成本。

function memoFib() {
  const c = new Map();
  let m = 0;
  let x1 = 0;
  let x2 = 1;
  return function* (x) {
    while (m <= x) {
      c.set(m, x1);
      [x1, x2] = [x2, x1 + x2];
      m++;
    }
    yield c.get(x)
  }
}
const fib = memoFib();
console.log(fib(10).next().value); // updates cache
console.log(fib(2).next().value);
console.log(fib(5).next().value);
console.log(fib(14).next().value); // updates cache
console.log(fib(11).next().value);
console.log(fib(1).next().value);

---

这是接下来的一个小步骤，将Trincot的递归示例扩展为一个记忆函数，该函数返回序列的特定范围作为迭代器。下面的代码片段使用数组作为缓存，而不是Map，并接受start和end索引，如果省略end，它将返回一个序列1。这样可以更好地利用生成器，并且由于缓存已经被顺序填充，因此数组比Map更适合。

function memoFib() {
  const c = [];
  let m = 0;
  let x1 = 0;
  let x2 = 1;
  return function* fib(start, end) {
    end = end ?? start + 1;
    while (m <= start) {
      c[m] = x1;
      [x1, x2] = [x2, x1 + x2];
      m++;
    }
    if (start < end) {
      yield c[start]
      yield* fib(start + 1, end)
    }
  }
}
const fib = memoFib();
console.log('Sequence:')
for (const n of fib(0, 5)) {
  console.log(n)
}
console.log('nSingle values:')
console.log(fib(2).next().value);
console.log(fib(11).next().value); // updates cache
console.log(fib(10).next().value);
console.log(fib(14).next().value); // updates cache