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

好好学习321
  • 171

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

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 更易于理解和操作,不知道我理解是否正确?

回复
阅读 846
2 个回答

递归,官话:

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

俗话:自己调用自己

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

动态规划,官话:

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

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

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

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

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

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

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

  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
}
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏