Efficiency of Forward vs. Backward Recursion in Dynamic Programming

Question

I have a question that has been bothering me for a while:

In our OR-introduction course, we introduce the concept of Dynamic Programming via backward recursion: Working backwards from a final state (at the final stage), until we have have reached a single initial state in stage 0. Introducing Dynamic Programming via backward recursion also seems to be the status quo in the textbooks.

However, these problems (for example: shortest path problems) can also be solved via forward recursion.

Why is it claimed then, that "backward recursion" usually performs faster than forward recursion? In the small "toy" problems that we address in the lecture, using either forward or backward recursion does not make a difference in the number of calculations that we do.

Especially coming from Dijkstra's Algorithm (which we introduce first) a more intuitive way would be to move through the network (and accordingly the different stages) in a forward fashion.

Note that these problems involve a specific known start state and a specific known end state and no uncertainty.

Also: When claiming that backward recursion executes faster: When I "reverse" the shortest-path-problem instance network [meaning: I come up with a problem instance that just interchanges start and finish node and the edges accordingly], then this would be the same as forward recursion of the original problem.

I have also taken a look at the following discussion, however I found the answers not very helpful / satisfactory: Stackexchange Discussion DP

Does this generally have to do with "keeping track of infeasible states" that we can only discard very late in the algorithm depending on whether we do forward or backward recursion?

Answer 1

First, what is Dynamic Programming? Everyone has its own definition. The one I use is "Solving a problem recursively, while storing the results of the sub-problems to avoid recomputing them multiple times".

---

Then, to exhibit a Dynamic Programming structure of a problem, the classical way is to find a recursive formula. Usually, it is more natural to write it the backward way.

For example, consider a shortest path problem between vertex $v_s$ and $v_t$ on a directed acyclic graph $G = (V, A)$ with distance $d$. Let $c(v)$ be the length of the shortest path to reach vertex $v$ from vertex $v_s$.

We have the following recursive formula: $$ c(v) = \left\{ \begin{array}{ll} 0 & \text{if $v = v_s$} \\ \min\limits_{u \in \cal{N}^-(v)} c(u) + d_{u,v} & \text{otherwise} \end{array} \right. $$

The value we are looking for is obviously $c(v_t)$.

Of course, it is possible to write it in the other direction. But it generally feels more natural this way.

My advice is, if you plan to implement a Dynamic Programming algorithm, write the recursive formula first on a paper before starting writing code, and clearly explicit the meaning of the objective.

---

Finally, once one has the recursive formula, comes the implementation. There are several ways to implement the recursive formula:

• Directly implementing the corresponding recursive function
• Computing all states iteratively
• Using list of states

Directly implementing the corresponding recursive function is the easiest way. One just needs to write a programming recursive function which first checks if the requested value has already been stored, and otherwise compute it and store it.

Pseudo-code for the example above:

def rec(v):
    if memory[v] is None:
        if v == vs:
            memory[v] = 0
        else:
            memory[v] = min(rec(u) + G.distance(u, v),
                            for u in G.predecessors(v))
    return memory[v]

memory = [None] * G.number_of_vertices()
rec(vt)

Computing all states iteratively requires to think a bit more. One needs to find the right order in which to compute the states. But this implementation is usually much faster. From my experience, I'd say that one can expect it to be about $10$ times faster than the recursive implementation. The reason behind this is not mathematical, but rather related to how cache works inside the computer: it's faster to access data which are stored next to each other in memory. You can find some experimental results for the Knapsack Problem on my Github

Pseudo-code for the example above:

memory = [None] * G.number_of_vertices()
vertices = G.vertices_sorted_in_topological_order()
memory[vs] = 0
for v in vertices:
    memory[v] = min(memory[u] + G.distance(u, v),
                    for u in G.predecessors(v))
memory[vt]

Using list of states is a bit more tricky, and it might not work in all cases. But when it works, it is usually the most efficient way, because it can be combined with other technics such as bounding. It is usually how state-of-the-art algorithms are implemented.

More details about these implementations can be found in:

• Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems. Springer Berlin Heidelberg, Berlin, Heidelberg https://link.springer.com/book/10.1007/978-3-540-24777-7

---

2 additional notes:

• The question you linked is not about Dynamic Programming, since there is no memorization.
• It is not obvious to consider Dijkstra's algorithm as Dynamic Programming. The example I gave is Bellman algorithm for the shortest path problem in a directed acyclic graph (with possibly negative weights), which is clearly Dynamic Programming.