2

Is it possible to solve any Dynamic Programming problem using recursion+memoization instead of using tabulation/iteration? Or there are some problems where it is must to use tabulation/iteration.

Also can we obtain the same time complexity when solving any problem using recursion+memoization ( I know space complexity differs and also recursion overhead cost exists).

Improve this question
11
  • It’s not entirely clear what you’re asking. In general, the generality of computation trivially implies that every iterative algorithm can be rewritten using recursion. Is that what you’re asking? Commented Jul 3, 2020 at 19:27
  • I know what you are saying. What I am asking is that can all dynamic programming problems be solved using recursive approach or there are some problems like subset sum which needs to be solve using tabulation to avoid NP caused due to recursive approach. Commented Jul 3, 2020 at 19:29
  • But using recursion does not imply not using tabulation. Both can be used in combination. Commented Jul 3, 2020 at 19:30
  • Yes and yes (as long as you use memoization with O(1)-time access). The main difference between recursive and iterative approach is that in the latter case you need to know the order in which you process subproblems. So in case of recursive approach, you do the same operations, but in a different order. Commented Jul 3, 2020 at 19:32
  • @Konrad RudolphThat is a different point. I want to know that using only recursion+memoization can we solve all the problems of dynamic programming. Commented Jul 3, 2020 at 19:32

1 Answer 1

Reset to default
4

Every Dynamic Programming problem can be expressed as recurrence relation which can be solved using recursion+memoization which can be converted into tabulation+iteration.

When you solve a DP problem using tabulation you solve the problem bottom up, typically by filling up an n-dimensional table. Based on the results in the table, the solution to the original problem is then computed.

When you solve a DP problem using memoization, you do it by maintaining a map of already solved sub problems. You do it top down in the sense that you solve the "top" problem first (which typically recurses down to solve the sub-problems).

The time complexity of a DP problem which uses tabulation+iteration is the same as an converted equivalent and correct memoization+recursion version of the solution. It is usually easy to find the time complexity in an tabulation+iteration method. On the other hand, memoization+recursion version of DP solution is more intuitive and readable.

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

11 Comments

Is it possible to solve subset sum problem using recursion+ memoization in polynomial complexity? Someone said to me that tabulation is used to get solution in polynomial time complexity not recursion.
Every recursive function/solution can be converted into an equivalent iterative version and vice-versa. Generally recursive solutions have more space-complexity but about the same time-complexity. I haven't much experience about subset-sum problem in particular but with the information mentioned above, I can say that its possible to solve the problem using recursion+memoization (as long as the memory doesn't become the bottleneck)
@Lucas with few quick searches online, I can see that there's no truly polynomial time-complexity solution available for subset-sum problem. Also, I can see that most online sources mention the time-complexity of both versions to be about the same for that problem.
Please see this link geeksforgeeks.org/subset-sum-problem-dp-25/?ref=rp before tabulation it is mentioning about NP for recursive approach.
@Lucas recursive approach is not the same as recursion+memoization. In simple naive recursion you will be calculating same sub-problems again and again whereas in the latter you will not. In the recursive approach mentioned in the link you posted, there's no memoization used and hence the higher time-complexity
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.