3
$\begingroup$

I am doing some exercises on dynamic programming in order to get familar with this concept. I've noticed that most of the time it's not difficult to calculate the complexity of a program using dynamic programming since most of the time we are recursively calculating a function $f$.

Let's suppose this function $f$ has $3$ parameters. This function $f$ represent all the subproblems of the problem we want to solve.

Moreover we have a nice recursive definition of $f$, so we are able to link the subproblems between each other and understand how a certain subproblem can help calculating an other subproblem.

Now suppose that the first parameter of our function $f$ can't take a value larger than $n_1$, the second also can't take a value larger than $n_2$ and the third parameter can't take a value larger than $n_3$. Supposing that calculating $f(i,j,k)$ takes $\mathcal{O}(m)$ then the complexity of our program is : (since it's essentially means we have $ n_1 \cdot n_2 \cdot n_3$ subproblems and each of these takes $m$ operations of constant cost to calculate)

$$\mathcal{O}(m \cdot n_1 \cdot n_2 \cdot n_3)$$

Now here comes my problem. If my program wants to calculate the maximum value of something then I can for example do the following :

$$f(i,j,k) = \max\{ f(i+1,j,k) + 1, f(i+1,j,k)\}$$

The problem is that this is not tail recursive. So in order to make the program tail recursive an idea could be to add a forth paramters to the function $f$, hence now we have :

$$f(i,j,k,l) = \max\{f(i+1,j,k,l+1), f(i+1,j,k,l)\}$$

This way the function $f$ is tail recursive.

Yet, my question is : making the function $f$ tail-recursive adds a $4$-th paramaters and hence increase the number of subproblems, so the complexity of our function is now increased (see what I said above about the complexity of a dynamic program), and hence tail recursion is bad on dynamic programs ?

Thank you.

Improve this question
$\endgroup$
9
  • $\begingroup$ "I've noticed that most of the time it's not difficult to calculate the complexity of a program using dynamic programming since most of the time we are recursively calculating a function f." -- are you considering implementations using memoization? (Also, not all recurrences are easy to solve.... I wish!) $\endgroup$ – Raphael♦ Nov 14 '18 at 14:12
  • $\begingroup$ @Raphael Yes I am considering implementation using memoization. In the case where we are using memoization, in order to calculate the complexity of the function $f$ we only need upper-bound on the parameters right ? So we don't need to solve recurrences relations ? $\endgroup$ – DP_q Nov 14 '18 at 14:15
  • $\begingroup$ (actually is it possible to do implementations that don't use memoization ? I mean memoization is the core of DP ? sorry, if I am asking to much questions here...) $\endgroup$ – DP_q Nov 14 '18 at 14:21
  • $\begingroup$ "I am considering implementation using memoization." It is harder to imagine DP without memoization. Just use it (unless in the rare cases, which you will know when you encounter them). $\endgroup$ – John L. Nov 14 '18 at 14:40
  • 1
    $\begingroup$ @Raphael Thank you very much for you answer. This is very interesting. So when attacking a DP problem most of the time it's easier to express the problem recursively since we understand the link between the subproblems. Then, in order to implement it we can use either recursion or memoization. The fact is that memoization is there so that we don't have to recalculate the subproblems so we use an array and nested loops. hence my missunderstanding comes from the fact that I was trying to do dynamic programming using recursion... and mixing the ideas of memoization and tail recursive... $\endgroup$ – DP_q Nov 14 '18 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.