递归和动态规划的区别，应该如何理解？

Question

递归和动态规划的区别，最好用例子，
在递归中，对数组的处理，比如说

const arr = [1, 2, 3, 4, 5, 6, 7]

function sum(i) {
  return i === 0 ? arr[0] : (arr[i] + sum(i - 1))
}

终止条件是 i等于 0，是否也可以把终止条件设置为 i = arr.length-1，只不过 i===0 更易于理解和操作，不知道我理解是否正确？

Answer 1

递归，官话：

递归（英語：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。 递归一词还较常用于描述以自相似方法重复事物的过程。 例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。 也可以理解为自我复制的过程。

俗话：自己调用自己

函数接受某一个具有“范围”特性的参数，将其“范围”缩小，就可以借助自身不断的将其缩小，最终缩小到一定程度认为是目标结果。

动态规划，官话：

动态规划（英語：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

俗话：走过的路我就不走了，已知的结论我就不去再运算了。

递归和动态规划从大面上说可能不是针对同一种问题，但是概念上或者说思路上是有一些相关的。直接一点，动态规划解决问题的时候会用到递归调用。当然也有的DP不需要递归，依赖一个数据结构。具体可以参考一下斐波那契的递归和非递归写法。

递归和DP可能都有一个“依赖上一次”或者“依赖之前”的感觉，递归可能就是传统的从调用栈的角度上来体现这种上下依赖关系（递归太深可能会爆炸），同样的，一些DP算法使用特殊的数据结构来维系上一次或者之前的结果（数据太多一样也有爆炸的可能性）。

至于给出的例子，我认为不可以改，你可以试一下改了之后sum(0)的结果。

已参与了 SegmentFault 思否社区 10 周年「问答」打卡 ，欢迎正在阅读的你也加入。

Answer 2

这俩没太大关系。。动态规划是解决问题的一种思路，递归是手段。
假如你要实现一个复杂页面，你有以下两种方案：

1. 对着原型图一个页面重头撸到尾，script里一个方法都没有，全是立即执行的内容，你每写一行代码都要考虑前面n行的代码，假设这时候你思维的复杂度是O(n), 代码量O(n)。
2. 你知道分治，所以你会先假设你要实现这个复杂的页面，你需要哪些模块，然后你再用相同的思路逐个将模块拆分为组件，再拆分成各个子文件。这时候你得到状态转移函数：
   页面=模块A + 模块B = 组件A + 组件B + ... = 文件A + 文件B + ... = 方法A + 方法B + 方法C + ...
   你按照这个模式来，你需要许多方法，但是写方法的时候只需要考虑IO, 分治后思考的难度降低到了O(logn)，但代码量可能还是O(n)。

你面对复杂问题知道了首先考虑解决这个问题，我需要什么东西，把一个复杂问题转移成若干子问题来实现。再回头看算法题，比如爬楼梯问题，假设n级台接，你一次只能爬一级或两级。
从第一级台接开始数可能性的话，思维的复杂度太大，所以反过来看，要得到f(n)，我需要什么。反过来看可以发现最后一级台阶只能从n-1级台接和n-2级台接到达，所以得到转移函数：
f(n) = f(n-1) + f(n-2)
可以得到代码如下：

const getCount = (n) => {
    if(n===1) return 1
    if(n===2) return 2
    return getCount(n-1) + getCount(n-2)
}

但是这么写会有太多重复计算，你计算getCount(n-1)的时候已经算过getCount(n-2)了，所以可以空间换时间，缓存计算过的结果：

const getCount = (n) => {
    const cache = {0: 1, 2: 2}
    const calc = (n) => {
        if(n in cache) return cache[n]
        const rst = calc(n-1) + calc(n-2)
        cache[n] = rst
        return cache[n]
    }
    return getCount(n-1) + getCount(n-2)
}

但是这么写又有一个问题，空间复杂度太高，cache中缓存了从1到n的结果，其实只需要n和n-1,所以迭代写法：

const getCount = (n) => {
    if(n===1) return 1
    if(n===2) return 2
    let past2 = 1
    let prev = 2;
    for(let i=3; i<=n; i++) {
        const val = past2 + prev
        past2 = prev
        prev = val
    }
    return prev
}