Recursion 思想

什么是递归，先看油管一位算法博主（LeetCode 小小福）的视频截图

利用递归的方式来计算斐波拉切数列

// 斐波拉切数列
// 1、1、2、3、5、8、13、21、34、55

// cache
const cache = {};

// 使用递归来计算出斐波拉切数列
function fib(n) {
  console.count("计数");
  // 缓存中有就直接拿缓存的
  if (cache.hasOwnProperty(n)) {
    console.count("命中缓存");
    return cache[n];
  }
  // 没有缓存就去重新计算
  const val = n === 0 || n === 1 ? 1 : fib(n - 1) + fib(n - 2);
  // 计算完，缓存起来
  cache[n] = val;

  return val;
}

for (let i = 0; i <= 9; i += 1) {
  console.log(fib(i));
}

// 如果没有缓存，计算重复次数是 276，有了缓存计数次数只有 26次 ，这还只是计算前9个数
// 所以利用好缓存，能让程序的计算速度有质的提升。以空间换时间

// 不用递归就非常简单

const arr = [1, 1];

while (arr.length <= 10) {
  arr.push(arr[arr.length - 1] + arr[arr.length - 2]);
}

// const cache = new Map();
// function fib(n) {
//   console.count("计数");
//   if (cache.has(n)) {
//     return cache.get(n);
//   }
//   const val = n === 0 || n === 1 ? 1 : fib(n - 1) + fib(n - 2);
//   cache.set(n, val);
//   return val;
// }
// for (let i = 0; i <= 9; i += 1) {
//   console.log(fib(i));
// }