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?