# Tail recursion can't work with dynamic programming programs

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.

• "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!) Commented Nov 14, 2018 at 14:12
• @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 ?
– DP_q
Commented Nov 14, 2018 at 14:15
• (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...)
– DP_q
Commented Nov 14, 2018 at 14:21
• "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). Commented Nov 14, 2018 at 14:40
• @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...
– DP_q
Commented Nov 14, 2018 at 19:31

I can tell yes... It is not working fine but you can go for some work around that I may not be preferable with. But recently I was working with 0/1 knapsack problem where If I go with the tail recursion approach or the head recursion approach that result it gives is correct. But If I try to apply DP(Dynamic Programming) in it. It is failing in the scence giving the wrong answer. let me give a sample input here

int n = 7;
vector<int>  weight = {6, 5, 1, 5, 6, 5, 9};
vector<int>  value = {5, 3, 4, 9, 6, 1, 1};
int maxWeight = 13;


If I use 2-D vector as my DP array to optimise it. I will paste the code below but here is now the function call and the values in DP are getting stored for this example I am taking the index of the weight vector and the maxWeight values f(0,13)->f(2,7)->f(2,2)->f(3,1)->f(4,1)->f(5,1)->f(6,1) and when returning back it start to store in dp like dp[6,1] = 12->dp[5,1] = 12->dp[4,1] = 12->dp[3,1] = 12->dp[2,2] = 12..... But it should not get stored in this way this is the problem with tail recursion where the result is also passed with the function so that the state changes are not captured correctly If you work out the full example we will get a clear clarity.

where as in the head recursion the ans or the result is not going to be returned that value will get added up as you can see in the below code so these mismatch of state won't occur.

#include <bits/stdc++.h>
using namespace std;

int kps_tail_rec(vector<int> &weight, vector<int> &value, int i, int &n, int maxWeight, int ans, vector<vector<int>> &dp) {
cout<<"start of func - > i= "<<i<<", maxWeight= "<<maxWeight<<endl;
if (i == n || maxWeight == 0)
return ans;

if (dp[i][maxWeight]){
cout<<"i= "<<i<<", maxWeight= "<<maxWeight<<" , dp[i][maxWeight] = "<<dp[i][maxWeight]<<endl;
return dp[i][maxWeight];
}

int taken = 0, nottaken = 0;

if (weight[i] <= maxWeight) {
taken = kps_tail_rec(weight, value, i + 1, n, maxWeight - weight[i], ans + value[i], dp);
}

nottaken = kps_tail_rec(weight, value, i + 1, n, maxWeight, ans, dp);
cout<<"for this i and maxWeight"<<i<<", "<<maxWeight<<"taken= "<<taken<<", nottaken= "<<nottaken<<endl;
return dp[i][maxWeight] = max(taken, nottaken);
}
int kps_head_rec(vector<int> &weight, vector<int> &value, int i, int &n, int maxWeight, vector<vector<int>> &dp) {
cout<<"start of func - > i= "<<i<<", maxWeight= "<<maxWeight<<endl;
if (i == n || maxWeight == 0)
return 0;

if (dp[i][maxWeight]){
cout<<"i= "<<i<<", maxWeight= "<<maxWeight<<" , dp[i][maxWeight] = "<<dp[i][maxWeight]<<endl;
return dp[i][maxWeight];
}

int taken = 0, nottaken = 0;

if (weight[i] <= maxWeight) {
taken = value[i] + kps_head_rec(weight, value, i + 1, n, maxWeight - weight[i], dp);
}

nottaken = kps_head_rec(weight, value, i + 1, n, maxWeight, dp);
cout<<"for this i and maxWeight"<<i<<", "<<maxWeight<<"taken= "<<taken<<", nottaken= "<<nottaken<<endl;
return dp[i][maxWeight] = max(taken, nottaken);
}

int knapsack(vector<int> weight, vector<int> value, int n, int maxWeight) {
vector<vector<int>> dp(n + 1, vector<int>(maxWeight + 1, 0));
cout << kps_tail_rec(weight, value, 0, n, maxWeight, 0, dp)<<"  , ";
cout<<" now going for the 2nd approch\n";
vector<vector<int>> dp1(n + 1, vector<int>(maxWeight + 1, 0));
cout << kps_head_rec(weight, value, 0, n, maxWeight, dp1);
return 0;
}

int main() {
int n = 7;
vector<int>  weight = {6, 5, 1, 5, 6, 5, 9};
vector<int>  value = {5, 3, 4, 9, 6, 1, 1};
int maxWeight = 13;
int result = knapsack(weight, value, n, maxWeight);
return 0;
}


Summary : In recurrsion both tail and head gives the same value but when we Optimise with DP going with Head recursion is a better option. enter code here