2

I know that every program that can be solved using dynamic programming can be solved using recursion, but is the vice versa also possible? If possible then how will the time complexity differ?

Improve this question
2
  • It can't really be answered unless you say what "solving a program using dynamic programming" means to you. In general it's not a precisely defined thing. For example, what would it mean for a program that sorts an array to use dynamic programming? Commented Jul 14, 2016 at 2:50
  • I asked it in general like if printing permutations of a string which can be done using recursion. can it be done using dynamic programming? Commented Jul 14, 2016 at 4:59

3 Answers 3

Reset to default
2

is the vice versa also possible?

Yes.

On the other hand, if you were actually meaning to ask:

is the vice versa also true?

Then reasonably speaking the answer is No. Not all problems that can be solved with recursive algorithms can reasonably be solved with dynamic programming. We only need to come up with one problem to highlight this: sorting. It is easy to solve the problem of sorting with a recursive algorithm, but there does not seem to be a reasonable algorithm to solve the problem of sorting with dynamic programming. Unfortunately I have to resort to using the weasel word "reasonable" here, because you could forcefully use dynamic programming in some manner to solve the problem of sorting, in a very awkward and inefficient way.

The question regarding the time complexity can't be answered. It depends on the problem at hand, and how applicable dynamic programming would be in solving the problem.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

If suppose we want to find permutations of a string which can be computed using recursion. Can the same question be solved using dynamic programming?
A problem must have two key properties for dynamic programming to be useful in solving the problem: overlapping sub-problems and optimal sub-structure. Does the problem of combinatorial generation (finding permutations of strings) have these two key properties?
It doesn't have overlapping sub problems. So that means it can't be solved using dynamic programming?
@Xylene23 as explained in my answer, I can't go as far as saying "it can't be solved using DP" because there could exist a DP algorithm to solve combinatorial generation. It's probably totally unnecessary, but this does not mean it's impossible.
1

A problem can be solved using dynamic programming if (1) it has optimal sub-structure, i.e. it is recursive, and (2) it has overlapping sub problems. Therefore, any recursive problem that has not overlapping sub problems cannot be solved using dynamic programming. Example: insertion sort, if defined recursively as sorted_list[0:n] = sorted_list[0] + sorted_list[1:n].

Improve this answer

Comments

-1

Dynamic Programming is a time-vs-complexity tradeoff. You store some information in tables so you do not need to recompute them if you need to do the same thing again.

If your problem naturally decomposes into subproblems that often repeat then dynamic programming is a good idea. On the other hand, if there are no recurring subproblems then there is no point in using dynamic programming.

Improve this answer

2 Comments

Doesn't really answer the question. Question has nothing to do with whether or when there is "no point in using dynamic programming". This is a theoretical question regarding whether a problem being solvable by recursion implies that it can also be solved using dynamic programming.
Well, I did say that. Whether dynamic programming will work for a general recursion problem depends on if you need recompute any subproblems during your computation. If there are no repeated substates then there is no gain from dynamic programming

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.