实现斐波那契数列 fibonacci

很早之前实现过这个，当时的目标是：

实现多个方法
实现单元测试
实现基准测试
1. 使用 benchmark 验证最优方法

现在重新研究这个问题，实现使用 JavaScript 尽可能快地来计算斐波那契数列

迭代方式 (for, while)
递归方法
尾递归优化
带缓存的递归
动态规划 DP

实现代码

/**
 * 迭代方式来实现斐波那契数列
 *
 * @param {number} n
 * @returns
 */
function iter(n) {
  let current = 0
  let next = 1
  for (let i = 0; i < n; i++) {
    ;[current, next] = [next, current + next]
  }
  return current
}

// while 同 for
function whileFn(n) {
  let current = 0 // 表示 f(n)
  let next = 1 // 表示 f(n+1)
  while (n--) {
    next += current
    current = next - current
  }
  return current
}

/**
 * 递归方式实现斐波那契数列
 *
 * @param {number} n
 * @returns
 */
function recurse(n) {
  if (n === 0) return 0
  if (n === 1) return 1
  return recurse(n - 1) + recurse(n - 2)
}

// 暴力递归，存在大量的重叠子问题
// 这就是动态规划问题的第⼀个性质：重叠⼦问题
// 子问题的个数 O(2^n), 算法的时间复杂度 O(2^n)

/**
 * 尾递归优化实现斐波那契数列
 *
 * @param {number} n
 * @returns
 */
function tail(n) {
  return fib(n, 0, 1)
}

/**
 * 尾递归优化
 *
 * @param {number} n
 * @param {number} current
 * @param {number} next
 * @returns
 */
function fib(n, current, next) {
  if (n === 0) return current
  return fib(n - 1, next, current + next)
}

// 带备忘录的递归解法（使用 memo 数组或哈希表充当备忘录）
// 备忘录相当于提供了一套“剪枝”操作，使递归数改造为不存在冗余的递归树，极大地减少了子问题

const memo = [0, 1]

function memoFib(n) {
  return helper(memo, n)
}

function helper(memo, n) {
  if (n === 1 || n === 2) {
    memo[n] = 1
    return memo[n]
  }
  if (typeof memo[n] !== 'undefined') {
    return memo[n]
  }
  memo[n] = helper(memo, n - 1) + helper(memo, n - 2)
  return memo[n]
}

// 无冗余计算
// 子问题时间复杂度 O(1), 子问题个数 O(n), 算法的时间复杂度 O(n)
// 比起暴力算法，强太多了
// 带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。
// 只不过这种方法叫做「自顶向下」，动态规划叫做「自底向上」

// 从一个规模较大的原问题，比如 f(20)，向下逐渐分解规模，直到触底，然后逐层返回答案，这就叫做「自顶向下」
// 反过来，直接从最底下，最简单、问题规模最小的开始往上推，直到推到我们想要的答案 f(20)，这就是动态规划的思路
// 这也是为什么动态规划一般都脱离了递归，而是有循环迭代完成计算。

// 动态规划

function dpFib(n) {
  if (n === 0) return 0
  if (n === 1 || n === 2) return 1

  const dp = [0, 1, 1]
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n]
}

// 「状态转移方程」
// 动态规划问题最困难的就是写出状态转移方程，就是暴力解
// 优化方法无非就是用备忘录或 DPtable，再无奥妙可言

// 继续思考
// 根据斐波那契数列的状态转移方程，可以看出当前状态只和之前的两个状态相关，
// 所以并不需要很长的 DPTable 来存储所有状态，字需要存储两个状态就行了
// 这样进一步优化，可以把空间复杂度从 O(n) 降为 O(1)

// Iterators_and_Generators
function* fibonacci() {
  var fn1 = 0
  var fn2 = 1
  while (true) {
    var current = fn1
    fn1 = fn2
    fn2 = current + fn1
    var reset = yield current
    if (reset) {
      fn1 = 0
      fn2 = 1
    }
  }
}

注意

使用动态规划这种思想解决问题的前提是，

一个问题当中必须有重复的子问题才能使用动态规划进行解决。

迭代 vs 递归

以下来自 GitHub Copilot

迭代和递归都是解决问题的方法，但它们的实现方式不同。

迭代是通过循环来重复执行一段代码，每次迭代都会更新变量的值，直到达到预期的结果。迭代通常使用 for 循环或 while 循环来实现，可以有效地处理大量数据和复杂的算法。迭代的优点是效率高，易于理解和调试，缺点是代码量较大。

递归是通过函数调用自身来解决问题，每次调用都会将问题分解为更小的子问题，直到达到基本情况。递归通常使用递归函数来实现，可以有效地处理树形结构和分治算法。递归的优点是代码简洁，易于理解和实现，缺点是效率低，容易导致栈溢出。

迭代和递归都可以解决同样的问题，但在不同的情况下选择不同的方法可以提高代码的效率和可读性。通常情况下，迭代更适合处理大量数据和复杂的算法，而递归更适合处理树形结构和分治算法。

生成器是一种特殊的迭代器，它可以通过函数来创建（不需要实现迭代器协议）。生成器函数使用 yield 语句来返回一个值，并暂停函数的执行，等待下一次调用。每次调用生成器函数时，它会从上一次暂停的位置继续执行，直到遇到下一个 yield 语句或函数结束。生成器可以用于生成大量数据或处理无限序列，例如斐波那契数列和素数序列等。

实现斐波那契数列 fibonacci ​

迭代 vs 递归 ​

实现斐波那契数列 fibonacci

迭代 vs 递归