递归

一个简单的递归阶乘

image.png

 j = (n) =>
      n === 1 ? 1
              : n * j(n-1)

image.png

斐波拉契数列

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

image.png

压栈/计算次数过高

image.png

如何降低压栈/计算次数

压栈：需要调用栈里记录“回到哪”

尾递归优化

用迭代替代递归

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)

image.png

尾递归的优势，可以不用“回头”，无需压栈

所有的递归都可以写成循环

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]
}

记忆化函数

记录之前的结果，而不是记录调用的状态

image.png

React 优化

React 优化

image.png

m没有变化
onClick就不需要重新执行
Child2就无须重新挂载，故Child也无需重新执行

const memo = (fn) => {
  const memoed = function(key) {
    if (!(key in memoed.cache)) {
      memoed.cache[key] = fn.apply(this, arguments)
        // 注意 memo 只会以第一个参数作为记忆点，但是还是会用 arguments 来调用 fn
    }
    return memoed.cache[key]
  }
  memoed.cache = {}
  return memoed
}

const x2 = memo((x) => {
    console.log('执行了一次')
    return x * 2
  })
  // 第一次调用 x2(1)
console.log(x2(1)) // 打印出执行了，并且返回2
  // 第二次调用 x2(1)
console.log(x2(1)) // 不打印执行，并且返回上次的结果2
  // 第三次调用 x2(1)
console.log(x2(1)) // 不打印执行，并且返回上次的结果2


// 执行结果

> "执行了一次"
> 2
> 2
> 2