# Is top-down dynamic programming always recursive?

I think top-down dynamic programming is mostly recursive (at least when we use memoization). For instance, solving the rod-cutting problem by this algorithm:

MEMOIZED-CUT-ROD(p, n):
let r[0..n] be a new array
for i = 0 to n:
r[i] = -\infty
return MEMOIZED-CUT-ROD-AUX(p, n, r)

MEMOIZED-CUT-ROD-AUX(p, n, r):
if r[n] >= 0:
return r[n]
if n == 0:
q = 0
else q = -\infty
for i = 1 to n:
q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n - i, r))
r[n] = q
return q


But is it always recursive? By recursive I mean we call the same function but with smaller parameters (Of course if this is the correct definition for recursive.)

Here's some text about dynamic programming from CLRS:

There are usually two equivalent ways to implement a dynamic-programming approach. We shall illustrate both of them with our rod-cutting example. The first approach is top-down with memoization. In this approach, we write the procedure recursively in a natural manner, but modified to save the result of each subproblem (usually in an array or hash table). The procedure now first checks to see whether it has previously solved this subproblem. If so, it returns the saved value, saving further computation at this level; if not, the procedure computes the value in the usual manner. We say that the recursive procedure has been memoized; it “remembers” what results it has computed previously. The second approach is the bottom-up method. This approach typically depends on some natural notion of the “size” of a subproblem, such that solving any particular subproblem depends only on solving “smaller” subproblems. We sort the subproblems by size and solve them in size order, smallest first. When solving a particular subproblem, we have already solved all of the smaller subproblems its solution depends upon, and we have saved their solutions. We solve each subproblem only once, and when we first see it, we have already solved all of its prerequisite subproblems.

• I don't think the question is well-formed. Recursion can always be converted to iteration, so the answer is no, depending on what you mean by your question.
– D.W.
Sep 8 at 7:00
• @D.W. The question is whether it can always be made nonrecursive or not. By recursive I mean we call the same function but with probably smaller parameters. According to what you said. we can always give an iterative version of recursive algorithms using a for or while loop. Is that right?
Sep 8 at 11:08
• If you want to clarify your question, you can edit it to clarify what you are asking.
– D.W.
Sep 10 at 18:14