LeetCode题解：2648. 生成斐波那契数列，迭代+递归，超详细解析

[chencl1986]

原题链接

https://leetcode.cn/problems/generate-fibonacci-sequence/

题目分析：

该题目要求我们实现一个生成器函数，用于产生斐波那契数列。斐波那契数列是一个由0和1开始，后续每个数字都是前两个数字之和的数列。题目给出的递推公式为 Xn = Xn-1 + Xn-2。

解题思路：

这个问题可以使用生成器函数的特性来解决。我们创建一个生成器函数，使用yield关键字在每次迭代中产生下一个斐波那契数。这个问题可以有两种解法，下面我们将分别介绍并解析这两种解法。

解法一：

var fibGenerator = function*() {
  let prev = 0
  let curr = 1

  while (true) {
    yield prev;
    [prev, curr] = [curr, prev + curr]
  }
};

在这个解法中，我们首先初始化了两个变量prev和curr，分别表示当前的斐波那契数和下一个斐波那契数。在每次迭代中，我们首先通过yield关键字产生当前的斐波那契数，然后更新prev和curr以准备产生下一个斐波那契数。

这里需要注意的是，由于yield会暂停函数的执行，因此[prev, curr] = [curr, prev + curr]这一行代码实际上是在yield暂停后，也就是在下一次迭代开始时执行的。这就保证了在每次迭代中，我们都能准确地产生出斐波那契数列中的下一个数字。

解法二：

var fibGenerator = function* (prev = 0, curr = 1) {
  yield prev;
  return yield* fibGenerator(curr, prev + curr);
};

在这个解法中，我们使用了yield*表达式，用于在当前生成器函数中产生另一个生成器函数的所有值。在每次迭代中，我们首先产生当前的斐波那契数，然后通过yield*关键字调用新的斐波那契生成器函数，以产生下一个斐波那契数。

这里需要注意的是，yield*表达式实际上会产生被委托生成器的所有值。因此，在yield pre产生当前斐波那契数后，return yield* fibGenerator(cur, pre + cur)就会开始产生下一个斐波那契生成器的所有值，也就是斐波那契数列中的下一个数字。

yield*是一个用于生成器函数中的语法，被称为委托给另一个生成器的 yield 表达式。yield* 关键字可以在生成器函数内部使用，可以产生另一个可迭代对象（例如另一个生成器函数，或者数组、字符串等）的所有值。

例如，我们可以使用 yield* 来处理数组：

function* iterateArray(array) {
  yield* array;
}

const arrayGen = iterateArray([1, 2, 3, 4, 5]);
console.log(arrayGen.next().value); // 1
console.log(arrayGen.next().value); // 2

或者我们也可以使用 yield* 来处理字符串：

function* iterateString(str) {
  yield* str;
}

const stringGen = iterateString("Hello");
console.log(stringGen.next().value); // 'H'
console.log(stringGen.next().value); // 'e'

yield* 在生成器函数中处理可迭代对象时，可以将对象中的每一个值产生出来。

在解法二中，yield* fibGenerator(cur, pre + cur) 表示把生成下一个斐波那契数的任务委托给了新的 fibGenerator(cur, pre + cur) 生成器函数。yield* 表达式的值为被委托的生成器最后一次 yield 的值或 return 的值。

让我们看一个更简单的例子来理解 yield* 的工作方式：

function* gen1() {
  yield 2;
  yield 3;
}

function* gen2() {
  yield 1;
  yield* gen1();
  yield 4;
}

var g = gen2();

console.log(g.next()); // { value: 1, done: false }
console.log(g.next()); // { value: 2, done: false }
console.log(g.next()); // { value: 3, done: false }
console.log(g.next()); // { value: 4, done: false }
console.log(g.next()); // { value: undefined, done: true }

在这个例子中，gen2 生成器函数在 yield* gen1() 时把控制权交给了 gen1 生成器函数，于是 gen1 的所有值（2 和 3）都被 gen2 产生出来。等到 gen1 生成完所有的值之后，控制权再次返回给 gen2，继续产生剩下的值。

因此，yield* fibGenerator(cur, pre + cur) 就会产生 fibGenerator(cur, pre + cur) 这个生成器函数的所有值，也就是斐波那契数列中的下一个数字。

总结：

以上就是生成斐波那契数列的两种解法及其解析。在实际编程中，生成器函数和 yield 关键字是非常有用的工具，可以帮助我们更方便地处理序列化的数据，并允许我们以需求驱动的方式来产生数据，而不是一次性产生所有数据。这种特性在处理大量数据或者需要流式处理数据的场景中特别有用。