问题标题: 递归和动规的区别

递归是通过函数自调用来节省空间

而动规则是通过消耗空间来节约时间

反正我觉得楼主说的对

刘宇唐在2020-08-26 19:03:39追加了内容

求采纳

差不多吧

不过如果你在递归中定义一个巨大数组就另当别论了[doge]

董子墨在2020-08-26 21:21:21追加了内容

但递归和dp真的很大有联系吗？

和dp有关系的是记忆化搜索吧

你说的应该是对的，但是做题能用动态规划的话，就不用递归吧，因为递归太消耗堆栈了

个人看法

记录下自己的理解

递归分为递推和回归，递归的递推是自上向下的，把大问题分解成小问题，等到最基本的不可再分的小问题解决了，回归解决大问题。

而动态规划只有递推，动态规划的递推是自下向上的，把小问题组合成大问题，先解决小问题然后推到解决大问题。

即递推从大问题入手，而动态规划从小问题入手解决。

动态规划用空间换取时间。

其实和你说的没什么大区别的，用斐波那契举例：

递归：

int fib(int n){  
     if(n>1) return fib(n-1) + fib(n-2);  
     else return n; // n = 0, 1时给出recursion终止条件  
}  

而动态规划：

 F[0] = 0;F[1] = 1;
 for(i = 2; i <= N; i++)
       F[i] = F[i-1] + F[i-2];

其实很像，整体很像迭代

继续看看递归和动规

递归的性质

一个具有递归性质的问题，大多具有两个特征，第一个是状态转移方程也就是递归方程，比如在求解阶乘时，n！=n*(n-1)!，就将求解n的阶乘转换为求解n-1的阶乘。第二个特征就是终止条件，一个递归是一类问题的求解，必定有一个结果

无法一只递归下去，有一个结束条件，也就是当问题规模简化的足够小的时候可以直接的出答案。

递归的代价

递归执行时，递归函数会被反复地调用，一层一层的进入，到达终止条件后，再一层一层出来，为了保证结果的正确性，每一层函数的运算结果和状态都必须保存在系统所分配的栈里面，当数据量很大的时候，递归所占用的空间和运行时间会非常恐怖，效率也很低

动态规划的性质

递归算法是从顶置低求解问题，而·动态规划算法是从低置顶求解问题，同样也需要状态转移方程方程，和初始条件，相较于递归算法的优势，动态规划算法不需要反复调用自身函数，也不需要储存每一层函数的状态，故而时间花费和空间花费都要少的多。

总结：动态规划的效率其实大于递归，递归在数据很大的时候是不太好的，我们都知道递推快于递归，递推相当于简单变形的动规，所以的话...各有所长，也都有其短，根据题目数据走是最好的

不能这么说，01背包的降维写法，可以不让空间爆掉，时间不变

递归：自上至下，把大问题分解成小问题解决。

动规：自下至上，通过解决小问题，集合为解决大问题。

用递归能解决的问题，一般都可以用动态规划来解决。

区别：

和你说的一样。

你说的都对

1