考虑计算斐波那契数列：
纯递归：
int fib(int x)
{
if (x < 2)
return 1;
return fib(x-1) + fib(x-2);
}
会导致指数级别的调用次数。
使用记忆化/动态规划的递归：
int fib(int x)
{
static vector<int> cache(N, -1);
int& result = cache[x];
if (result == -1)
{
if (x < 2)
result = 1;
else
result = fib(x-1) + fib(x-2);
}
return result;
}
现在我们有线性数量的调用，第一次是线性的，以后都是常数时间。
上述方法被称为“延迟计算”。我们在第一次需要时计算早期项。
以下方法也被视为动态规划，但不使用递归：
int fibresult[N];
void setup_fib()
{
fibresult[0] = 1;
fibresult[1] = 1;
for (int i = 2; i < N; i++)
fibresult[i] = fibresult[i-1] + fibresult[i-2];
}
int fib(int x) { return fibresult[x]; }
这种方式可能被描述为“急切”，“预缓存”或“迭代”。虽然总体上更快，但我们必须手动确定子问题需要计算的顺序。对于斐波那契数列来说很容易，但对于更复杂的DP问题，这变得更加困难，因此如果懒惰递归方法足够快，我们就会回退到懒惰递归方法。
另外，以下内容既不是递归也不是DP：
int fib(int x)
{
int a = 1;
int b = 1;
for (int i = 2; i < x; i++)
{
a = a + b;
swap(a,b);
}
return b;
}
这种方法使用恒定的空间和线性时间。
此外，为了完整起见，我想提到一个闭合形式的斐波那契数列计算方法，它既不使用递归也不使用动态规划，而是使用基于黄金比例的数学公式，使我们能够在常数时间内计算出斐波那契数列的项：
http://www.dreamincode.net/forums/topic/115550-fibonacci-closed-form/
f(3)，然后稍后再次调用 f(3)，只有第一次进行计算，第二次调用从第一次缓存的结果获取。这通常被认为是DP的一种形式。 - Andrew Tomazos递归加上记忆化正是动态规划的一种具体“口味”：按照自顶向下的方式进行动态规划。
更确切地说，并没有要求特别使用递归。任何与记忆化结合的分治算法都是自顶向下的动态规划。（递归是分治法中后进先出（LIFO）的一种，“先进先出”（FIFO）或其他任何类型的分治法也可以使用。）
因此，更准确地说：
divide & conquer + memoization == top-down dynamic programming
另外，从非常正式的角度来看，如果你为一个不生成重复子问题（意味着没有记忆化优势）的问题实现了分治算法，那么你可以声称这个分治算法是“动态规划”的一种退化示例。
然而，动态规划是一个更一般的概念。动态规划可以使用自底向上的方法，这与分治+记忆化不同。
我相信您可以在互联网上找到详细的定义。这是我简化事情的尝试。
递归是再次调用自身。
动态规划是一种解决具有特定结构（最优子结构）问题的方法，其中问题可以被分解为与原始问题类似的子问题。显然，可以使用递归来解决DP问题。但是这并不是必需的。可以在没有递归的情况下解决DP问题。
记忆化是一种优化依赖于递归的DP算法的方法。重点是不要重新解决已经解决的子问题。您可以将其视为子问题的解决方案缓存。
a -> call a
a -> call b, b -> call c, c -> call a
动态规划是指利用较小子问题的解来解决更大问题的方法。通常情况下，这种解法最容易通过递归实现，因为你通常会以递归函数的形式考虑这种解法。但是，迭代实现通常更受欢迎，因为它需要更少的时间和内存。
记忆化技术用于避免递归DP实现所需的时间过长。大多数情况下，DP算法将在解决多个大问题时使用相同的子问题。在递归实现中，这意味着我们将多次重新计算相同的内容。记忆化意味着将这些子问题的结果保存到表中。在进入递归调用时，我们检查其结果是否存在于表中：如果是，则返回该结果；如果不是，则计算它，将其保存在表中，然后返回它。
递归与记忆化和动态规划完全没有关系，它是一个完全独立的概念。
否则，这是一个重复的问题：动态规划和记忆化：自底向上 vs 自顶向下方法