递归与动态规划？简简单单明明白白的入门指南

近来不少准备入行的同学在群里询问递归方面的算法题，这可是大佬们装X的大好机会，不少人热心解答，可谓是其乐融融了。直到有同学提出，明明三行就能写完你们搞这么麻烦干嘛？大佬：要不你fn(1000)试试？然后就没有然后了，这究竟发生什么。

什么是递归

官方解释：

程序调用自身的编程技巧称为递归（ recursion）。很容易理解，在js中不就是一个函数调用了他自己，套娃了起来，你中有我，我中还是我.....

斐波那契数列

看个最常见的例子吧，我们著名的斐波那契数列。有一个数列，从第三位开始，每个数字都是前两位数的相加，1, 1, 2, 3, 5, 8, 13, 21, 34, 55............. 那么第n位的值是什么呢？

首先我们假设有一个函数能够计算出这个结果，这个函数输入一个参数n，代表第n位，函数的返回结果是数列第n位的值，函数取个名叫recursion，也就是recursion(n)。

function recursion(n) {
    return '数列第n位的值'
}

数列要求每个数字都是前两位数的相加，n的前两位也就是n-1、n-2，他们相加要等于第n位的值，所以recursion(n) = recursion(n-1) + recursion(n-2)。

function recursion(n) {
    return recursion(n-1) + recursion(n-2)
}

上面我们抽象出了数列的计算方法，当然我们知道这是有条件的，n必须大于等于3，因为小于3就没有前两位值了，又哪来的两个值相加。

function recursion(n) {
    if ([1, 2].includes(n)) {
      return 1
    } else {
      return recursion(n - 1) + recursion(n - 2)
    }
}

三步，我们很快就写完了一个递归函数，并且得出的结果完全正确。但是这样真的就可以了么？

recursion(3) recursion(5) recursion(10)都没有问题，当你recursion(100)，浏览器未响应了！！？？

发生了什么？我们简单的检测下函数的运行时间。

console.time('10')
console.log(recursion(10))
console.timeEnd('10')

console.time('20')
console.log(recursion(20))
console.timeEnd('20')

console.time('30')
console.log(recursion(30))
console.timeEnd('30')

console.time('40')
console.log(recursion(40))
console.timeEnd('40')

控制台输出结果如下：

我们发现n的每次增加，运行时间都在成几何级数的暴增，这里面发生了什么。打上断点，我们来看看栈：

似乎看不出什么，但是栈内需要执行函数的数量，随着数值的增大暴增中....

什么导致了调用堆栈的暴增

假设我们计算recursion(3)，进入函数，就会变成计算一次recursion(1)和一次recursion(2)，总计2次
假设我们计算recursion(4)，进入函数，就会变成计算一次recursion(3)和一次recursion(2)也就是两次的recursion(2)和一次recursion(1)，总计3次
假设我们计算recursion(5)，最后会变成三次recursion(2)和两次recursion(1)，总计5次

一次类推，每次增加一，最后计算的总次数也会相当于斐波那契数列的增长，当我们recursion(100)时，总计需要计算354224848179262000000次，(¬‿¬)这浏览器不爆炸才有鬼。

怎么解决

既然我们知道了原因，那我们就来处理一下这个重复计算的问题。

调用堆栈的暴增来源于相同函数的重复计算，那我们最容易想到的就是用一个数组进行存储，每次遇到新的值，计算出结果后我们都储存到数组中，当重复使用时，就直接使用数组中的值！说干就干。

首先增加一次存储数组，我们知道当n=1或2时，值为1，数组的0位置随便占下位。

let cache = [null, 1, 1]

然后在函数中，如果recursion(n)的值已经在数组中存在，就直接返回数组中的值

if (cache.includes(n)) {
    return cache[n]
}

最后，如果数组中不存在就计算这个值，然后存到数组里

else {
    if (!cache[n - 1]) cache[n - 1] = recursion(n - 1)
    if (!cache[n - 2]) cache[n - 2] = recursion(n - 2)
    return cache[n - 1] + cache[n - 2]
}

整体代码如下:

let cache = [null, 1, 1]
function recursion(n) {
    if (cache.includes(n)) {
        return cache[n]
    } else {
        if (!cache[n - 2]) cache[n - 2] = recursion(n - 2)
        if (!cache[n - 1]) cache[n - 1] = recursion(n - 1)
        return cache[n - 1] + cache[n - 2]
    }
}

简单的测试下:

console.time('1000')
console.log(recursion(1000))
console.timeEnd('1000')

控制台输出结果：

控制台结果

我们可以看出，在数列的第1000位，数值已经是相当大了，但是计算时间仅要0.35ms（毕竟是O(n)的复杂度啊），而如果换成不带存储的，怕是算上几十年都出不来（栈不会溢出的话）。

数列我们计算出来了，并且复杂度也极低，这就是最优的解法了么？当然不是，来看看我们的动态规划吧！

动态规划

仔细观察我们储存数组方法的调用堆栈，我们发现其实在计算时，浏览器一次次推进堆栈的其实是按n从大到小的，最后在出栈计算时，相当于从n=2计算到了n=max，那我们为什么不能直接从小到大计算这个存储数组呢，最后计算到我们第n位就结束，这不是更加简单？

说干就干，我们写一个数组，然后从2到n进行循环，最后输出数组的最后一位。

function dp(n) {
    const arr = [1, 1]
    for (let idx = 2; idx < n; idx++) {
        arr[idx] = arr[idx - 1] + arr[idx - 2]
    }
    return arr.pop()
}

如此简单就完成了斐波那契数组的计算，并且复杂度也是O(n)。

当然如果你不喜欢for循环，并且想要一行写完的话也是可以的，不过你要知道基础的for循环在js中是性能最高的遍历方式了，其他的写法可以更好看，更装，但是性能上来说还是for循环应该被优先选择。

function dp(n) {
    return new Array(n - 2).fill('').reduce((pre) => [...pre, pre[pre.length - 1] + pre[pre.length - 2]], [1, 1]).pop()
}

例子我们说完了，那我们聊聊遇到这样的问题，应该怎么整理思路解决呢？

首先，我们要先整理问题的状态方程，相当于我们例子中的fn(n) = fn(n-1) + fn(n-2)
然后我们需要确认问题的边界条件，相当于例子中，n需要>2，n=1、n=2时结果都为1
最后正向的计算结果值，直至获取到我们需要的结果

而当我们难以理清这个思路时，不妨按照我们今天求解斐波那契数列的思路，先想想递归如何解决，然后再想想这个存储数组如何生成，最后理清动态规划的思路。

这篇文章结合了个人对递归、dp的理解和实际例子的演示，希望对初学js的同学们有所启发！

递归与动态规划？简简单单明明白白的入门指南 ​

什么是递归 ​

官方解释： ​

斐波那契数列 ​

什么导致了调用堆栈的暴增 ​

怎么解决 ​

动态规划 ​