Is top-down dynamic programming always recursive?

Question

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.

• D.W.: 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.
• Emad: @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?
• D.W.: If you want to clarify your question, you can edit it to clarify what you are asking.

Answer 1

I think the short answer here is: There is no such thing as top-down dynamic programming.

The definition of a recursive function is a function that calls itself. In dynamic programming, we find solutions for subproblems before building solutions for larger subproblems.

• Emad: But CLRS uses this expression. I'll add the text to my question now.
• Ainsley H.: @Emad It's in the Dynamic programming chapter, but if you read carefully (I believe) they talk about bottom-up method being dynamic programming, and the top-down with memoization being recursion.
• Emad: At the beginning of the chapter It says that dynamic programming is typically bottom-up, but (looks like) not always. And Maybe being recursive and dynamic programming are not in contrast here. (in the top-down case)