考虑计算斐波那契数列：

纯递归：

int fib(int x)
{
    if (x < 2)
        return 1;

    return fib(x-1) + fib(x-2);
}

导致通话次数呈指数增长。

带备忘录/ DP的递归：

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;
}

现在，我们第一次具有线性的呼叫数，此后保持不变。

上面的方法称为“惰性”。我们会在首次要求时计算较早的术语。

以下内容也将被视为DP，但无需递归：

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;
}

它使用恒定的空间和线性时间。

另外，为完整性起见，我还会提到斐波那契的封闭形式，它使用下位递归或DP，这使我们能够在固定时间内使用基于黄金比率的数学公式来计算斐波那契项：

http://www.dreamincode.net/forums/topic/115550-fibonacci-closed-
form/