今天就简单来谈谈这几者之间的关联和区别
递归
一句话，我认为递归的本质就是将原问题拆分成具有相同性质的子问题。
递归的特点：
1、子问题拆分方程式，比如：f(n) = f(n-1) * n
2、终止条件：也就是子问题无法再进一步拆分时，这时可以直接求出解，退出递归。
一个问题能否使用递归求解，就看能不能满足上面两个特征
以数值的整数次方为例
通过分析，我们很容易的知道上面这道题是非常符合递归特征的
1、子问题拆分方程式：f(x, n) = f(x, n-1) * x
2、终止条件：if n < 2: return x
class Solution(object):def myPow(self, x, n):""":type x: float:type n: int:rtype: float"""# 因为题目n有可能为负数，因此这里需要判断if n == 0:return 1if n > 0:return self.abs_pow(x, n)if n < 0:abs_val = self.abs_pow(x, -n)return 1 / abs_valdef abs_pow(self, x, n):# 该递归函数只处理n为正数，n为负数时，由调用方反除一下即可。if n < 2:return xrst = self.abs_pow(x, n-1)return x * rst
因为递归的调用栈时有深度限制的，因此这道题是没法AC的
有时候我们会遇到很多这样的情况，那么怎么解决调用深度的问题呢，很容易想到递归的兄弟迭代。
迭代
我们知道递归和迭代其实是天生一对的，本质是一样的，迭代只是我们自己模拟了递归的调用栈而已，因此迭代一般会用到栈这样的数据结构
当然由于这道题比较简单，用不到栈，只是一个数的叠乘而已
def abs_pow(self, x, n):rst = 1while n > 0:rst *= xn -= 1return rst
递归和迭代在二叉树用的非常多，二叉树基本天生就跟递归一起的，因为思路简单，符合人们的正常思维，只要有递归的地方，都可用转换为迭代，大家可以自己使用二叉树的题目来练习练习递归和迭代。
分治
其实，我认为递归算法从本质上来说都是分治算法，无非就是有些问题递归需要将原问题分解成多个子问题，而有的只需要分解成一个子问题，因此有的人将前面那种情况称作分治，将后面那种情况称作递归。
之前说过，递归跟迭代是一一对应的，因此分治有两种解法: 递归和迭代
分治算法的思想：
1、数学归纳法：只要出现可以用数学归纳公式来表示的大规模问题，第一反应就应该想到分治算法，通过特定的函数参数安排，一定可以用同一个函数来表述不同规模的问题，套用递归结构，可迅速解决问题！
2、不一定使用递归结构：递归结构是循环结构的一种，也是分治思想应用最多的一种程序结构，但是不一定要使用它！关键在于能够写出递归公式以及是否有必要使用递归算法。
因此可以知道，分治是一种算法思想，递归是一种技术手段。
分治算法的特征：
1、分解：将原问题拆分成若干个子问题
2、求解子问题：也就是终止条件
3、合并：将各个子问题的解合并，形成原问题的解
下面以斐波那契数列为例：
class Solution(object):def fib(self, n):""":type n: int:rtype: int"""if n <= 0:return 0# 备忘录memo = [0] * (n+1)return self.f(n, memo)def f(self, n, memo):# 终止条件if n in [1, 2]:return 1if memo[n] != 0:return memo[n]# 分解n1 = self.f(n-1, memo)n2 = self.f(n-2, memo)# 合并memo[n] = (n1 + n2) % 1000000007return memo[n]
注：分治算法一般体现在归并排序和快速排序里面
从这道题可以看出：
1、在求解该问题的时候，有很多重复的子问题，这样会导致非常低效，于是我们加了缓存，也就是带备忘录的递归解法，
2、整个解法是自顶向下的，通过画递归树就很容易的看出来。比如f(20)，向下逐渐分解，知道f(1)和f(2)，然后触底返回。
回溯
回溯其实类似于DFS搜索算法，以二叉树为例：
1、从根节点出发
2、随便选择一个子节点并达到该子节点，并标记该节点
3、然后从该子节点又随便选择一个子节点并到达该子节点，直到到达叶子节点
4、此时我们已经完整的做了一次选择，但是我们发现，在根节点到叶子节点的路径中，我们还有很多选择可以做。因此，我们需要从叶子节点往上一层层的返回，每返回一个节点，都选择一个之前没有走过的节点继续走下去，也就是重复2/3/4步骤，直到遍历完整个二叉树。
说了这么多，那么回溯跟上面讲的几个算法有什么联系呢：
我们来看下回溯算法的几个特征就知道了
回溯算法的特征：
1、深度优先遍历dfs：回溯算法一般采用dfs求解，因此满足递归的一般特征
2、子集：回溯题目一般都要求求解所有的最优解，因此，dfs的终止条件就是判断是否得到了一个最优解，然后直接返回。
3、遍历空间集：在每一轮dfs中都需要遍历空间集，根据题目性质，有的需要从0开始，有的需要从当前位置开始。
4、剪枝：在遍历空间集的时候，需要优先将不符合条件的去除掉，不然会做很多无用的递归调用，导致超时。
5、加入元素：遍历空间集的时候，加入每一个元素，然后再dfs
6、移除元素：当一轮dfs达到终止条件结束的时候，说明当前选择已经完成，需要返回到上一轮做其他选择，因此需要将上一轮选择时加入的元素删除掉。
这很抽象，我们以组合总和为例
class Solution(object):def combinationSum(self, candidates, target):""":type candidates: List[int]:type target: int:rtype: List[List[int]]"""rst = []# 先对列表排序，便于剪枝candidates.sort()self.dfs(rst, [], candidates, target, 0)return rstdef dfs(self, rst, sub_rst, candidates, target, start):# 终止条件：一般就是判断是否找到了一个最优解if sum(sub_rst) == target:rst.append(sub_rst[:])return# 遍历空间集：从当前位置出发for index in range(start, len(candidates)):# 加入每一个元素sub_rst.append(candidates[index])# 判断是否超过了总和，是则直接返回（因为前面我们已经排过序了）if sum(sub_rst) > target:sub_rst.pop()break# 开始dfs下一轮：因为这道题目要求每一个数字可以重复使用，因此下一轮的start也是当前位置# 有的题目要求不能重复使用，那么这里的index应该改为 index+1self.dfs(rst, sub_rst, candidates, target, index)# 已经完成一轮dfs，开始返回上一轮做其他选择，先将本轮的选择去掉sub_rst.pop()
动态规划
动态规划也简称dp，动态规划的定义是什么，我也不知道，各有各的理解吧
动态规划的特征：
1、最优子结构：在自下而上的递推过程中，我们求得的每个子问题一定是全局最优解，既然它分解的子问题是全局最优解，那么依赖于它们解的原问题自然也是全局最优解。
2、重叠子问题：在求解原问题的时候，我们往往需要依赖其子问题，子问题依赖其子子问题，甚至可能同时依赖多个子问题，因此子问题之间是有重叠关系的。
3、状态初始化：因为动态规划是依赖子问题的，因此需要先初始化已知状态，从而才能自下而上的递推到原问题得解。
4、遍历状态集：首先根据需要求解的结果来确定状态集，然后遍历状态集，更新状态dp
5、状态转移方程：也就是每一级子问题之间的关系式。
下面以最长回文子串为例
class Solution(object):def longestPalindrome(self, s):""":type s: str:rtype: str"""len_s = len(s)if len_s < 2:return s# 因为是判断子串，根据子串的性质s[i:j]，因此必然涉及到两层循环，也就需要定义二维数组dp# 状态初始化：默认为True，可以省去很多计算dp = [[True for _ in range(len_s)] for _ in range(len_s)]max_len = 0start = 0# 状态转移方程：表示i到j的子串是否是回文子串# dp[i][j] = (s[i] == s[j] and dp[i+1][j-1])# 遍历状态集：因为需要知道j-1，因此j需要从1开始for j in range(1, len_s):# 因为是子串，i一定是要小于jfor i in range(j):if s[i] == s[j]:# 如果收尾字符相等，那么直接取决于去掉该收尾的子串dp[i][j] = dp[i+1][j-1]else:# 如果不相等，不管子串如何，肯定不是回文dp[i][j] = False# 更新最大长度if dp[i][j] and max_len < j - i:max_len = j - istart = ireturn s[start:start+max_len+1]
从这道题可以看出：
整个解法是自底向上的，也就是先得到dp[0][0]，然后逐渐的扩大范围，最终得到dp[0][n]
这跟前面递归和分治时提到的自顶向下，形成对比。
贪心
贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。
贪心算法的特征：
1、最优子结构：贪心算法也是将原问题分解成多个性质相同的子问题，每个问题都是局部最优。
2、贪心选择性质：在做贪心选择时，我们直接做出当前子问题中看起来最优的解，这也是贪心算法和动态规划的不同之处。
3、遍历状态集：遍历状态集，做出局部最优选择，更新结果。
4、无后效性：某个状态以后的过程不会影响以前的状态，只与当前状态有关。
下面以为例
class Solution(object):def canJump(self, nums):""":type nums: List[int]:rtype: bool"""if not nums:return Falselen_nums = len(nums)max_pos = 0# 遍历状态集for i in range(len_nums):if i > max_pos:return False# 对每一个状态选择都做局部最优解max_pos = max(max_pos, i + nums[i])if max_pos >= len_nums-1:return Truereturn False
这里提下
涉及到贪心算法的核心性质：
只适用于求解可行解，不适用于求最值以及所有解
后记
《算法之道》对其中的三种算法进行了归纳总结，如下表所示：
作者：tunsuy
链接：https://leetcode-/circle/article/yXFal5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
java达人
ID：drjava
（长按或扫码识别）
