你能用 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;
}

发电机很棒。话虽这么说 - 它们也适用于递归任务，因为您可以执行它们 'lazily'.

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

到目前为止我想出的方法没有用。

所以我想知道：您将如何在 JavaScript 中执行递归的记忆斐波那契生成器函数？

Answer 1

一些初步意见：

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

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 的回答很好地涵盖了你问题的递归生成器方面，我同意他们对这种情况下的记忆的评估。由于看起来您正在寻找 return 特定的斐波那契数，您可以简单地记住您在问题中发布的函数（减去异步，因为这里不需要）。请记住，由于它只会产生一次，因此它可以很容易地成为标准函数，因为无论您何时访问 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 递归示例扩展为记忆函数，return将系列的特定范围作为迭代器。下面的代码片段使用数组作为缓存而不是 Map 并接受 start 和 end 索引，如果省略 end 它将 return 序列 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

你能用 js 生成器做一个递归的、记忆化的斐波那契函数吗？

Can you do a recursive, memoized Fibonacci function using a js generator?

javascript

generator

fibonacci

memoization