斐波那列

第三项 = 第二项 + 第一项
1、1、2、3、5、8、13、21、34、55、89、144、233、377、610、987、1597、2584、4181、6765

代码

function fib(n) {
  if (n === 1 || n === 2) {
    return 1
  }
  return fib(n-1) + fib(n-2)
}

console.time('fib time');
console.log(fib(20))
console.timeEnd('fib time')

// 6765
// fib time: 1.222900390625 ms

优化-自顶向下

function fibHelper(n) {
  const cache = []
  function fib(n) {
    if (n === 1 || n === 2) {
      return 1
    }
    if (!cache[n]) {
      cache[n] = fib(n-1) + fib(n-2)
    }
    return cache[n]
  }
  return fib(n)
}
// 6765
// fibHelper time: 0.18994140625 ms

优化-自底向上

function fibHelper(n) {
  const cache = []
  cache[1] = cache[2] = 1
  for (let i = 3; i <= n; i++) {
    cache[i] = cache[i-1] + cache[i-2]
  }
  return cache[n]
}

console.time('fibHelper time');
console.log(fibHelper(20))
console.timeEnd('fibHelper time')

// 6765
// fibHelper time: 0.16015625 ms

优化-自底向上-优化

function fibHelper(n) {
  let prev = 1
  let cur = 1
  
  for (let i = 3; i <= n; i++) {
    const sum = prev + cur
    prev = cur
    cur = sum
  }
  return cur
}

console.time('fibHelper time')
console.log(fibHelper(20))
console.timeEnd('fibHelper time')
// 6765
// fibHelper time: 0.167236328125 ms

尾递归

function fib(n, ac1 = 1, ac2 = 1) {
  if (n <= 1) {
    return ac1
  }

  return fib(n - 1, ac2, ac1 + ac2)
}

console.time('fib time')
console.log(fib(20))
console.timeEnd('fib time')
// 6765
// fib time: 0.129150390625 ms