斐波那契数列

预计阅读时间: 小于 1 分钟

斐波那契数列：F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2)

解决方法

递归

1function fib(n) {
2  if (n < 2) return n;
3  return fib(n - 1) + fib(n - 2);
4}

但这样的方式会导致当求解数量过大的时候，递归层数很深，运行时间长。

所以可以在递归里面加个map 来缓存已经计算过的数据

优化

1const map = new Map();
2
3function fib(n) {
4  if (n < 2) return n;
5  if (map.has(n)) return map.get(n);
6  const res = fib(n - 1) + fib(n - 2);
7  map.set(n, res);
8  return res;
9}

这份代码如果放在单一解决某个问题的文件运行是没问题的，但如果作为一个hook 来使用的话，因为map 的定义在外部作用域，会对外层作用域变量造成污染，所以将map 的声明改成函数内部。

1function fib(n, map = new Map()) {
2  if (n < 2) return n;
3  if (map.has(n)) return map.get(n);
4  const res = fib(n - 1, map) + fib(n - 2, map);
5  map.set(n, res);
6  return res;
7}

看似没啥问题了，重新写一个函数，返回一整个斐波那契数列

1function fibs(n) {
2  const res = [];
3  for (let i = 0; i <= n; i++) {
4    res.push(fib(i));
5  }
6  return res;
7}

函数导出

由于现在有两个函数了，但是对于fibs 函数里面的循环中，每次调用fib 函数都会实例化一个map，但这是放在在外层的，在fib 函数引用了外部的map 变量（闭包）。

1function createFibFunction() {
2  const mp = new Map();
3
4  function fib(n) {
5    if (n < 2) return n;
6    if (!mp.has(n)) {
7      const res = fib(n - 1) + fib(n - 2);
8      mp.set(n, res);
9    }
10    return mp.get(n);
11  }
12
13  function fibs(n) {
14    const res = [];
15    for (let i = 0; i <= n; i++) {
16      res.push(fib(i));
17    }
18    return res;
19  }
20
21  return { fib, fibs };
22}

最后，将两个方法进行导出就能提供给外部使用了

1const { fib, fibs } = createFibFunction();
2export { fib, fibs };

reduce

在reduce中，有点像for循环遍历叠加，参数中有四个参数：

参数	说明	是否必选
total	初始值，每次迭代后返回的结果	✔️
currentVal	当前遍历到的元素	✔️
currentIndex	当前遍历到的元素下标	❌
arr	当前元素所属的数组对象	❌

1function fibs(n) {
2  return Array.from({ length: n }).reduce((res, _, index) => {
3    if (index < 2) {
4      res.push(1);
5    } else {
6      res.push(res[index - 1] + res[index - 2]);
7    }
8    return res;
9  }, []);
10}

Array.from({ length: n }) 是为了构造一个长度为n的数组。

还可以通过增加一个函数来给数组里面每个值赋值：Array.from({length:9},(_, index)=> index)

生成器

迭代器的作用就是可以是数据结构可以通过循环遍历，比如Array、Object、Map和Set。

他们都可以通过调用next()方法进行迭代

自定义迭代器

在Object中可以自定义实现一个Symbol.iterator 来自定义迭代器方法，在next()方法中通过返回{done: 是否终止, value: 返回值}来判断关闭（没法继续遍历）。

1const obj = {
2  arr: [1, 2, 3, 4, 5],
3  [Symbol.iterator]() {
4    let index = 0;
5    return {
6      arr: this.arr,
7      next() {
8        if (index < 5) {
9          return {
10            value: this.arr[index++],
11            done: false,
12          };
13        }
14        return {
15          value: undefined,
16          done: true,
17        };
18      },
19    };
20  },
21};
22for (let i of obj) {
23  console.log(i);
24}

而生成器就是在ES6新增的一个结构，拥有在一个函数块内暂停和恢复代码执行的能力。

在声明生成器只需要在function前面加一个星号(*)，通过yield 关键字进行暂停，通过调用该生成器返回实例的next() 方法恢复执行。

1function* fibIterator(n) {
2  let now = 1,
3    next = 1,
4    count = 0;
5  while (true) {
6    yield now;
7    [now, next] = [next, now + next];
8    count++;
9    if (count >= n) {
10      return;
11    }
12  }
13}
14
15function fibs(n) {
16  const iterator = fibIterator(n);
17  const res = [];
18  for (let i of iterator) {
19    res.push(i);
20  }
21  return res;
22}

另外一种解法，利用take(n)会给定n个迭代次数的迭代器。

1function* fibIterator(i = 1, j = 1) {
2  while (!(yield i)) [i, j] = [j, i + j];
3}
4
5console.log([...fibIterator().take(10)]);

完整code

1// getFib.js
2function createFibFunction() {
3  const mp = new Map();
4
5  function fib(n) {
6    if (n < 2) return n;
7    if (!mp.has(n)) {
8      const res = fib(n - 1) + fib(n - 2);
9      mp.set(n, res);
10    }
11    return mp.get(n);
12  }
13
14  function fibs(n) {
15    const res = [];
16    for (let i = 0; i <= n; i++) {
17      res.push(fib(i));
18    }
19    return res;
20  }
21
22  return { fib, fibs };
23}
24
25const { fib, fibs } = createFibFunction();
26export { fib, fibs };

1<!-- test.html -->
2<!doctype html>
3<html lang="en">
4  <head>
5    <meta charset="UTF-8" />
6    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
7    <title>Document</title>
8  </head>
9
10  <body>
11    <script type="module">
12      import { fib, fibs } from './getFibFunction.js';
13      console.log(fib(10), fibs(10)); // 55 [0,1,1,2,3,5,8,13,21,34,55]
14    </script>
15  </body>
16</html>

知识点

闭包

如果一个函数需要用到外部的变量或者两个函数需要借助一个变量来传递就可以用闭包。

模块导出

模块导出的作用就是为了能让外部文件访问到该文件里面的变量、方法和类

分类

分别导出

1export const a = 1;
2export function test() {
3  console.log('test');
4}
5
6// 引入
7import { a, test } from './test.js';

统一导出

1const a = 1;
2function test() {
3  console.log('test');
4}
5export { a, test };
6
7// 引入
8import * as myFunc from './test.js';
9console.log(myFunc.a); // 1
10console.log(myFunc.test()); // test

默认导出

1function test() {
2  console.log('test');
3}
4export default test;
5
6// 引入
7import myFunc from './test.js';
8console.log(myFunc.test()); // test

总结

找到一个问题的解决方式之后可以思考有没有优化的地方（时间、空间、代码可读性、接口使用方便性）。
写一个模块的时候要在外面调用更加方便，比如我这里一开始如果是导出export createFibFunction，在调用模块的时候就还需要去实例化，但换成最终那样子的话就可以直接调用fib 和 fibs 方法了。

#斐波那契数列

#解决方法

#递归

#优化

#函数导出

#reduce

#生成器

#自定义迭代器

#完整code

#知识点

#闭包

#模块导出

#分类

#总结