斐波那契数

递归知识

• (1)递归：函数自己调用自己
• (2)递归的"缺陷"：递归到一定程度，会发生"栈溢出"
• (3)递归的"时间复杂度"：递归总次数*每次递归的次数
• (4)递归的"空间复杂度"：递归的深度*每次递归空间的大小（注意："每次递归空间的大小"是个常数，可以基本忽略不计） 递归的"深度"：树的高度（递归的过程是一个"二叉树"）

递归

• 时间复杂度O(2^n)，准确是 O(1.618^n)
• 空间复杂度：O(n)
• 缺点：1.重复计算，2.函数递归容易爆栈

function fibonacci(n) {
  if (n < 1) { return 0 }
  if (n <= 2) { return 1 }

  return fibonacci(n - 1) + fibonacci(n - 2)
}

解决解决重复计算问题 方法一

• 自顶向下记忆化
• 时间复杂度O(2^n)，准确是 O(1.618^n)
• 空间复杂度：O(n)
• 缺点：时间复杂度过高，函数递归容易爆栈

const map = new Map()
function fibonacci(n) {
  if (n < 1) { return 0 }
  if (n <= 2) { return 1 }

  if (map.has(n)) {
    return map.get(n)
  }

  const res = fibonacci(n - 1) + fibonacci(n - 2)
  map.set(n, res)

  return res
}

解决解决重复计算问题 方法二

• 时间复杂度O(2^n)，准确是 O(1.618^n)
• 空间复杂度：O(n)
• 缺点：时间复杂度过高，函数递归容易爆栈

function fibonacciMemoization() {
  const memo = [0, 1]
  return function fibonacci(n) {
    if (memo[n] != null) { return memo[n] }

    return memo[n] = fibonacci(n - 1) + fibonacci(n - 2)
  }
}

尾递归

• 时间复杂度O(n)
• 空间复杂度：O(n)
• 缺点：时间复杂度过高，函数递归容易爆栈

function fibonacci(prev, next, n) {
  if (n < 3) {
    return 1
  }

  if (n === 3) {
    return prev + next
  }

  return fibonacci(next, prev + next, n - 1)
}

fibonacci(1, 1, n) // n 是常量

动态规划

• 自底向上记忆化，动态规划
• 时间复杂度：O(n)
• 空间复杂度：O(n)

function fibonacci(n) {
  if (n < 1) { return 0 }
  if (n <= 2) { return 1 }

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

  return res[n]
}

以上方法缺点：res 的数组随着 n 增大而增大，可以持续优化，因为斐波数就是前2个数相加得到，把数组的长度保持改为2

优化内部数组长度，自底向上记忆化，动态规划，压缩数组

• 时间复杂度：O(n)
• 空间复杂度：O(1)

function fibonacci(n) {
  if (n < 1) { return 0 }
  if (n <= 2) { return 1 }

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

继续优化空间复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(1)
• 这个性能最好

function fibonacci(n) {
  if (n < 1) { return 0 }
  if (n <= 2) { return 1 }

  let prev = 1
  let next = 1
  let res = 0
  for (let i = 3; i <= n; i++) {
    res = prev + next
    prev = next
    next = res
  }
  return res
}