Dynamic Programming

Dynamic programming (DP) is a style of programming suited for combinatorial optimization (for example, the knapsack problem). Instead of using brute force to try every possible combination to solve a problem, an implementation based on dynamic programming optimizes the solution by computing and caching intermediate results in order to avoid redundant computations. Recursion can be used exclusively to solve such a problem but at a higher computational cost.
Let's calculate a couple of members in the Fibonacci series using recursion and DP.

Fibonacci sequence

F_n = F_n-1 + F_n-2

1, 1, 2, 3, 5, 8, 21, ...

where the next number in the sequence is the sum of the previous two numbers.

Objective

Calculate the sixth and seventh number in the Fibonacci series. The corresponding numbers in the series are 8 and 21.

Fibonacci sequence using recursion

public int Calculate(int n)
{
    if (n <= 2)
        return 1;
    else
        return Calculate(n - 1) + Calculate(n - 2);
}

Call Stack - Calculate(6)

Calculate(6)
Calculate(5)
Calculate(4)
Calculate(3)
Calculate(2)
Calculate(1)
Calculate(2)
Calculate(3)
Calculate(2)
Calculate(1)
Calculate(4)
Calculate(3)
Calculate(2)
Calculate(1)
Calculate(2)

Call Stack - Calculate (7)

Calculate(7)
Calculate(6)
Calculate(5)
Calculate(4)
Calculate(3)
Calculate(2)
Calculate(1)
Calculate(2)
Calculate(3)
Calculate(2)
Calculate(1)
Calculate(4)
Calculate(3)
Calculate(2)
Calculate(1)
Calculate(2)
Calculate(5)
Calculate(4)
Calculate(3)
Calculate(2)
Calculate(1)
Calculate(2)
Calculate(3)
Calculate(2)
Calculate(1)

The Issue - Inefficiency

As n increases, so do the number of recursions to solve the problem. Compare the number of calls to Calculate() method in the two stack traces. Note the redundant calls to Calculate methods for n=5 and n=4.
Using recursion Fib(n) is solved in exponential time.

T(n) = T(n-1) + T(n-2) + Θ(1)

// Θ(1) constant part

Fibonacci sequence using DP

int?[] m_CachedResults = new int?[short.MaxValue + 1];
     
public int DPCalculate(int n)
{
    m_CachedResults[1] = 1;
    m_CachedResults[2] = 1;

    if (m_CachedResults[n] != null)
    {
        return m_CachedResults[n].GetValueOrDefault();
    }
    else
    {
        m_CachedResults[n] = Calculate(n);
        return m_CachedResults[n].GetValueOrDefault();
    }
}

private int Calculate(int n)
{
    if (n <= 2)
        return 1;
    else
    {
        if (m_CachedResults[n] != null)
            return m_CachedResults[n].GetValueOrDefault();
        else
            return Calculate(n - 1) + Calculate(n - 2);
    }
}

Call Stack - Calculate(6)

Calculate(6)

Calculate(5)

Calculate(4)

Calculate(3)

Calculate(2)

Calculate(1)

Calculate(2)

Calculate(3)

Calculate(2)

Calculate(1)

Calculate(4)

Calculate(3)

Calculate(2)

Calculate(1)

Calculate(2)

Call Stack - Calculate (7)

Calculate(7)

Calculate(6)

Calculate(5)

Calculate(4)

Calculate(3)

Calculate(2)

Calculate(1)

Calculate(2)

Calculate(3)

Calculate(2)

Calculate(1)

Result - Efficiency

Since the program utilizes DP and caches intermediate values (memoized values), the calculation of the subsequent fibonacci numbers in the sequence is much more efficient. As the cache results get filled out, the algorithm becomes progressively more efficient.

Memoized calls are constant Θ(1)
For a given n, only one recursion cycle is used. Over time and multiple accesses, this is essentially constant. Therefore, the DP algorithm for Fibonacci calculation is linear (n).