函数递归, 记忆化, React优化

函数递归, 记忆化, React优化

Posted by limantang on November 13, 2019

函数递归, 记忆化, React优化

要想理解函数递归先要理解递归的含义

这里就不在铺开讲了, 可以看一下博客中递归的那篇文章详细讲解的递归 这里强调一下递归的几个特点

  • 层层递进, 然后层层回归 层层递进其实就是函数的不断压栈 层层回归: 当一次递进过程结束的时候, 就是层层回归的开始, 也就是 压如栈中的函数不断的弹出, 回归一次弹出一次, 计算得到一次结果
  • 函数不断压栈的过程其实保留函数现场的过程

举个🌰

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

如果上面的过程看做一座山的话, 上山的过程就是层层递进, 函数不断压栈 将函数当时的所需要现场保存下来, 为了弹栈时计算使用 下山的过程就是层层回归, 函数不断弹栈, 然后不断的执行计算函数

递归的优化

首先举一个稍微复杂一点的递归函数🌰 计算斐波那契数列

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

其实这个例子是为了说明, 有的递归计算过程中会存在大量的重复计算, 就好比上面的这个例子, 重复的计算了f(2), f(1), f(0)这几个函数 这样会大大的降低性能 打开控制台可以试验一下f(48)执行所需要的时间, 在我的电脑上大约执行了48秒才得到结果, 可见执行浪费的时间很多

那么如果优化上面的情况呢 有两种办法

  1. 使用尾递归 说一个之前第一次听到尾递归这三个字时闹出的笑话, 第一次听到尾递归时我误以为是伪递归, 就理解成的假的递归, 就是伪递归😆, 和真递归正好是相反的呢…

上面的代码可以使用尾递归代替进行优化

f = (n) => f_helper(2, n, 1, 0)

f_helper = (start, end, prev1, prev2) => 
	start === end ? prev1 + prev2
			: f_helper(start + 1, end, prev1 + prev2, prev1)

这段代码就是尾递归的实现, 看着可能有些难以理解, 下面分析一下这段代码

首先明确一下尾递归的过程就是迭代的过程, 每一次迭代的结果都会替代上一次迭代的结果, 而不会保留上一次迭代的结果

其中start是迭代开始的记录

end是迭代结束的记录

prev1是前一项的结果

prev2是前两项的结果

由于斐波那契数列第一二项是已知的, 所以start从2开始, 前一项也就是prev1是1, 也就是数列的第二项, 同理prev2是0 每一次迭代计算得到的结果都作为下一次迭代函数执行的参数, start都要加1, 所以下一次迭代的前一项prev1就是上一次迭代的prev1 + prev2 下一次迭代的前两项prev2就是上一次迭代的前一项prev1(这个计算方式是根据斐波那契数列计算规则所得, 并不是尾递归就是这个计算规则, 不要弄混) 直到start === end也就是到达了迭代的终点, 也就得到了结果

如果还是不明白可以结合我上面的分析自己画画图理解一下😆

为什么说尾递归是递归的优化呢, 在函数执行过程中, 看着也是函数嵌套, 自己调用自己, 为什么性能就比递归优秀呢

  • 尾递归是不存在函数压栈的过程的, 函数压栈主要是为了保留现场, 等到函数真正执行的时候可以回到正确的现场, 回到正确的位置, 但是尾递归是没有层层回归的这个过程的, 可以体会一下上面的分析过程, 尾递归不需要为函数保留现场

但是对于JS来说, 目前为止JS没有完全实现尾递归优化的, 还是存在函数不断压栈的情况, 不断弹栈, 虽然说尾递归不需要为函数保留现场 对于有尾递归优化的语言, 这段优化的代码可以节省很多压栈弹栈的次数

所有的递归都可以使用循环来表示(不知道谁说的😃)

如果你觉得递归性能不好, 尾递归又比较难写, 难以理解 可以使用循环来重新实现递归

还是举斐波那契数列的🌰

f = (n) => {
	let array = [0 ,1];
	for (let i = 2; i <= n - 2; i ++) {
		array[i] = array[i - 1] + array[i - 2]
	}
	return array[array.length - 1];
}

这个性能很好, 为什么性能很好呢, 因为省去了很多重复的计算, 例如递归当中, 重复计算多次的f(2), f(1), f(0), 在循环当中只计算一次, 因为每次计算的结果都保存在数组当中了

使用记忆化优化递归

记忆化最大的优点就是大大的降低了递归过程中重复计算, 也就是减少很多不必要的函数执行, 也就是大大减少了函数的压栈弹栈操作, 极大的提升了性能

具体可以看看Loadsh中记忆化函数的实现, 以后会单独讲解一下记忆化函数的实现, 本篇文章就不涉及了

记忆化不仅仅可以优化递归, 只要是涉及到函数重复执行的都可以使用记忆化进行优化

举一个React通过记忆化优化的🌰

代码地址

React-CodeSandbox

React-CodeSandbox