递归

程序调用自身的编程技巧称为递归（ recursion）。 递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模
较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
通常来说，为了描述问题的某一状态，必须用到该状态的上一个状态；而如果要描述上一个状态，又必须用到上一个状态的上一个状态…… 这样用自己来定义自己的方法就是递归。

动态规划和递归的关系

DP是一种解决问题的思路，与它对标的是贪心，枚举等的解题策略。
而递归指的则是一种具体的操作，与它对标的应该是循环，选择等实操。
在某些情况下，递归和循环是可以相互转化的，例如斐波那契数列的推导。
递归实际上是利用函数调用时返回上层函数的特性来保存之前的操作信息，并以此来简化操作，但也带来了过度占用栈空间的问题。所以，对于依赖于这种特性的操作将其转化为循环就需要额外的添加一个记录单元，例如树和图的遍历。
而DP实际上是通过对子问题结果的记录，并通过状态转移方程的方式进行推导，一步一步的演算出最终的结果。以此使得在推理更大的问题时，子问题的数据具有可复用性，类似于函数带来的代码复用的效果，最终达到对暴力解法进行剪枝的目的。

动态规划：一种解决问题的算法思想。与之同属于算法思想的有：枚举（暴力）、分治、贪心等。
递归：一种具体的代码结构，即在本函数中调用了本身。与之同属于代码结构的有：递推（迭代）。
因为动态规划的状态转移方程（即递推公式）就用到了递归，如 f(n) = f(n-1) + f(n-2)，所以我们自然而然很容易想到用递归代码结构来实现动态规划。但，递归会多次重复求解同一个子问题，导致不必要的开销。所以，我们在用动态规划思想解决问题时，一般用迭代的方式（如 for 循环）实现，这样就避免了多次重复计算同一个子问题。
因此，动态规划和递归的关系可以理解为：动态规划是解决问题的一种算法思想，具体的实现可以用递归。

例题

题：437

参考资料