Possibly the worst named thing in computing? Not only is "programming" not referring to programming, but "dynamic" is meaningless and just there to try to make it sound fancy.
I prefer "cached recursion".
I prefer "cached recursion".
The memoized recursive function is an implementation methodology on a digital computer that specifically side-steps the question of in which order one should do the tabulation. I would argue that recursive memoization is a possible solution technique to dynamic programming problems (defined as the universe of problems that admit a dynamic programming solution,) but strictly speaking, in and of itself, is not dynamic programming.
Memoisation is a more general tactic that hands more of the busy work over to the computer.
I didn't say that recursion and caching are the opposite of dynamic, I said they are essentially orthogonal concepts to it.
Generally speaking, dynamical systems are systems that have some sort of dependence on time [1]. In dynamic programming we have an optimization/decision problem in which time plays an essential role. The optimality is measured with respect to the whole time evolution. Bellmann showed that you can break this intertemporal optimization down into individual time steps.
So the key observation of dynamic programming is how to turn an "all times at once" problem into a "one time at a time" problem.
The reason that Hamilton's name shows up next to Bellmann here is that physicists and mathematicians (Lagrange, Hamilton, Jacobi) figured out that you can do the inverse: You can write the dynamical equations of physics as an intertemporal (all times at once) optimization problem. This has been one of the most influential ideas in theoretical physics _ever_, especially after Noether's theorems leveraged this structure to connect symmetries and conserved quantities. In many fields of theoretical physics you no longer write down differential equations to model a dynamical system, you write down a "Lagrangian", and mean that your system follows those trajectories that minimize the integral of the Lagrangian over all time. So the central ideas of dynamic programming are extremely tightly related to physics and dynamical systems.
[1] https://en.wikipedia.org/wiki/Dynamical_system
Edit: After reading a bit more I think I understand why people focus on this. The algorithmic examples with shortest paths sort of show the point. To me the core point of Dynamic Programming is before you start thinking about recursion or memoization. It's when you establish that you have optimal substructures:
https://en.wikipedia.org/wiki/Optimal_substructure
what is dynamical is that the subproblems depend on each other, in the way that what happens at time t+1 depends on what happens at time t, or, more to the point, what is the optimal decision at time t depends on what the optimal decision at time t+1 is. If your subproblems are ordered by time, then of course you don't need recursion to solve them, you just iterate over time steps, hence my confusion.
If we set aside the fact that the term "dynamic" was apparently chosen here basically because it sounded cool, and for no good reason, and are trying to retroactively redefine it in a way where the word has meaning, then:
With recursion the computation order is predefined and deterministic.
With dynamic programming the computation order is more flexible since the core of the technique is just memoizing prior work. Your DP solution could be organized in recursive top-down fashion, or more optimally in bottom-up fashion if the algorithm is strictly recursive by nature, or neither of the above.
i.e. With dynamic programming in general you are just reusing results if/when they exist, else calculating them - it a more "go with the flow" dynamic approach than recursion where the order of calls is strictly prescribed.
Also: the core of dynamic programming is breaking down a global optimization problem into many interacting local pieces. The Bellmann equation, which is the core mathematical result of dynamic programming, features neither recursion nor memoization.
It reminds also of "blackboard-based" AI systems where a bunch of cooperating agents with different capabilities jointly work on a problem by posing sub-problems and sharing them on a common blackboard where other agents can grab them and post a solution back on the board.
1) the recursion solution is often too slow, but uses little memory.
2) the memoization solution can make the algorithms from 1 a lot faster, but blows up memory use.
3) the dynamic programming solution only keeps the previous partial solutions in memory that will be needed for future partial solutions. Therefore it is the "Minimal Memory Memoized" solution. It often requires a smart ordering of partial solutions that allows for the earliest cache eviction.
Your "cached recursion" sounds like number 2 to me, and the crux about dynamic programming is to figure out when to remove an entry from your cache.
Can you give an example of this? I don't think that is correct. But we might be saying the same thing, because in practice by the time you achieve minimal memory, you will have a bottom-up solution.
Is your comment that this is higher than the memory requirement of the recursive solution, because that doesn't seem correct to me? The recursive solution also has O(N) memory, which is the depth of the tree it is searching.
If you go bottom up, you don't need any memoization. You just keep the paths and compare them, discarding the ones that are guaranteed to be suboptimal. This way initially, you will have N paths of length 1 (the leaves) and each step up you will have -1 path to keep, where the paths grow by 1 element.
If you go recursively from the top, then you don't know anything about the lower levels and thus must "fork" into left and right branch at each step, until you reach the bottom, from which you start filling the cache with the results of subproblems.
Of course one problem of using a global cache is, that parallelizing this becomes ugly and requires a mutex, while in contrast with the bottom up idea you can cleanly separate, because you don't need any global state at all.
We had a different characterisation in one of our mathematical optimisation classes: dynamic programming is basically every problem that isomorphic to finding the longest path in a graph, with suitable 'overloading' of 'maximum' (for picking among multiple alternative paths) and 'addition' (for combining multiple sub-paths).
First, to illustrate what I mean by this overloading: matrix multiplication usually has multiplication () and addition (+). However, in the min-plus-algebra you overload (+) with minimum and () with plus, and then multiplying matrices becomes equivalent to hopping two paths in the adjacency matrix of a graph. (Sorry, if this is a bit confusing.) Specifically, taking an adjacency matrix A and calculating A* := 1 + A + AA + AAA + ... is equivalent to taking the transitive closure of edge hopping in your graph, ie the shortest paths between all pairs of vertices.
If you overload (+) with maximum and () with plus instead, you can find longest paths. For that to make sense, you should not have cycles in your graph.
Now let's go back to dynamic programming: the shared optimal sub-structure property of dynamic programming is exactly the same as what you have in finding longest paths.
The structure might sound overly restrictive, but you'll find that it works for all (most?) examples of dynamic programming.
P.S. My recollection was a bit vague, so I asked ChatGPT for some help, and apparently I wasn't completely wrong: https://chatgpt.com/share/687de24c-c674-8009-9984-0fda56d1c1...
P.P.S. Despite everything I said above, I agree that 'cached recursion' is still a better name than dynamic programming.