Node-JS专精03递归记忆化

递归

阶乘

1
2
3
4
5
6
7
8
9
10
11
12
const j = (n) => 
                n === 1 ? 1 
                        : n * j(n - 1)

j(4)
= 4 * j(3)
= 4 * ( 3 * j(2))
= 4 * ( 3 * 2 * j(1))
= 4 * ( 3 * 2 * 1)
= 4 * ( 3 * 2 )
= 4 * 6
= 24

斐波那契数列

1
2
3
4
const fib = (n) =>
            n === 0 ? 0 :
            n === 1 ? 1 :
            fib(n - 1) + fib(n - 2)

递归的过程

  • 压栈
    • 弹匣压入子弹
  • 出栈
    • 从弹匣(栈顶)拿出子弹

而上面的几个例子利用的就是方法栈

调用栈用来记忆“回到那”

  • 如果记忆过多，就会爆栈

如果降低压栈次数

  • 尾递归优化 (使用迭代代替递归)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
f = (n) => f_inner(2,n,1,0)

f_inner = (start, end, prev1, prev2) => 
    start === end ? prev1 + prev2
        : f_inner(start + 1, end , prev1 + prev2, prev1)
// 这就是尾递归

// 还可以写成循环
f = (n) =>{
    let array = [0,1]
    for(let i=0;i< n - 2;i++){
        array[i+2] = array[i+1] + array[i]
    }
    return array[array.length - 1]
}
  • 记忆化函数

记忆化

可以大量减少重复计算

Lodash 实现

1
2
3
4
5
6
7
8
9
10
11
_.memoize = function(func, hasher) {
    var memoize = function(key) {
      var cache = memoize.cache;
      var address = '' + (hasher ? hasher.apply(this, arguments) : key)
      if (!has(cache, address))
          cache[address] = func.apply(this, arguments)
          return cache[address];
    };
    memoize.cache = {};
    return memoize;
};

React记忆化

React.memo 减少计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import React from "react";
import ReactDOM from "react-dom";

import "./styles.css";

function App() {
  const onClick = () => {
    setN(n + 1);
  };
  const [n, setN] = React.useState(0);
  return (
    <div className="App">
      <div>
        <button onClick={onClick}>update {n}</button>
      </div>
      <Child />
      <Child2 />
    </div>
  );
}

function Child() {
  console.log("child 执行了");
  return <div>Child</div>;
}

function Child_2() {
  console.log("child2 执行了");
  return <div>Child2</div>;
}

const Child2 = React.memo(Child_2);

const rootElement = document.getElementById("root");
ReactDOM.render(<App />, rootElement);

解析

  • 如果你用函数式组件，那么每次setN 都会导致执行 Child() 里的打印
    • 如果 Child() 里有定义变量，那么也会重新执行，非常浪费
  • 优化就是使用 React.memo减少计算 记忆化组件(把结果缓存起来)

一个新的问题每次 onclick都会重新创建

1
2
3
4
5
6
7
const onClickChild = React.useCallback(() => {
    console.log(m);
}, [m]); 
// 第一个参数是 执行的函数
// 第二个参数是 它依赖于什么 如果 m 变了 则它重新执行

只要 m 不变 onClickChild 就不会重新执行