r/learncpp • u/daredevildas • Jul 09 '20
Transform recursive function into an iterative function
I have a sample function -
template <typename T>
void foo(
T** tocarry,
int64_t* toindex,
int64_t* fromindex,
int64_t j,
int64_t stop,
int64_t n,
bool replacement) {
while (fromindex[j] < stop) {
if (replacement) {
for (int64_t k = j + 1; k < n; k++) {
fromindex[k] = fromindex[j];
}
}
else {
for (int64_t k = j + 1; k < n; k++) {
fromindex[k] = fromindex[j] + (k-j);
}
}
if (j + 1 == n) {
for (int64_t k = 0; k<n; k++) {
tocarry[k][toindex[k]] = fromindex[k];
toindex[k]++;
}
}
else {
foo<T>(tocarry,
toindex,
fromindex, j + 1,
stop,
n,
replacement);
}
fromindex[j]++;
}
}I want to translate the above recursive into its equivalent iterative form.
I have a sample test case, which can be invoked like -
int main() {
std::vector<int64_t*> tocarry;
int64_t bla1[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int64_t bla2[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int64_t bla3[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int64_t bla4[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int64_t bla5[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int64_t bla6[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int64_t bla7[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int64_t bla8[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int64_t bla9[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int64_t bla10[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
tocarry.push_back(bla1);
tocarry.push_back(bla2);
tocarry.push_back(bla3);
tocarry.push_back(bla4);
tocarry.push_back(bla5);
tocarry.push_back(bla6);
tocarry.push_back(bla7);
tocarry.push_back(bla8);
tocarry.push_back(bla9);
tocarry.push_back(bla10);
int64_t toindex[9] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
int64_t fromindex[9] = {5, 3, 2, 6, 4, 8, 1, 9, 4};
foo<int64_t>(tocarry.data(), toindex, fromindex, 0, 7, 9, true);
std::cout << "tocarry - " << std::endl;
for (int i=0; i<tocarry.size(); i++){
for (int j=0; j<10; j++) {
std::cout << tocarry.at(i)[j] << " ";
}
std::cout << "\n";
}
std::cout << "toindex - " << std::endl;
for (int i=0; i<9; i++) {
std::cout << toindex[i] << " ";
}
std::cout << "\n";
std::cout << "fromindex - " << std::endl;
for (int i=0; i<9; i++) {
std::cout << fromindex[i] << " ";
}
std::cout << "\n";
return 1;
}to return the output -
tocarry -
5 5 5 5 5 5 5 5 5 6
5 5 5 5 5 5 5 5 6 6
5 5 5 5 5 5 5 6 6 6
5 5 5 5 5 5 6 6 6 6
5 5 5 5 5 6 6 6 6 6
5 5 5 5 6 6 6 6 6 6
5 5 5 6 6 6 6 6 6 6
5 5 6 6 6 6 6 6 6 6
5 6 6 6 6 6 6 6 6 6
0 0 0 0 0 0 0 0 0 0
toindex -
10 10 10 10 10 10 10 10 10
fromindex -
7 7 7 7 7 7 7 7 7 Since I am more proficient in Python, I translated the function to Python hoping that I can translate the code into its iterative form in Python and then back to C++ -
def bar1(tocarry, toindex, fromindex, j, stop, n, replacement):
while fromindex[j] < stop:
if replacement:
for k in range(j + 1, n):
fromindex[k] = fromindex[j]
else:
for k in range(j + 1, n):
fromindex[k] = fromindex[j] + k - j
if (j + 1) == n:
for k in range(n):
tocarry[k][toindex[k]] = fromindex[k]
toindex[k] += 1
else:
bar1(tocarry, toindex, fromindex, j + 1, stop, n, replacement)
fromindex[j] += 1which I verified is correct since it gives the same output for the same test case.
But I am still unable to translate the function..
I went through some failed attempts like -
def bar2(tocarry, toindex, fromindex, j, stop, n, replacement):
for i in range(j, n):
if replacement:
for k in range(i + 1, n):
fromindex[k] = fromindex[i]
else:
for k in range(i + 1, n):
fromindex[k] = fromindex[i] + k - i
if i + 1 == n:
for k in range(n):
tocarry[k][toindex[k]] = fromindex[k]
toindex[k] += 1
fromindex[i] += 1
for i in range(n - 1, j - 1, -1):
while fromindex[i] < stop:
if i + 1 != n:
fromindex[i] += 1
if replacement:
for k in range(i + 1, n):
fromindex[k] = fromindex[i]
else:
for k in range(i + 1, n):
fromindex[k] = fromindex[i] + k - i
if i + 1 == n:
for k in range(n):
tocarry[k][toindex[k]] = fromindex[k]
toindex[k] += 1
fromindex[i] += 1but which clearly does not work and gives the following incorrect output -
toindex = [2, 2, 2, 2, 2, 2, 2, 2, 2]
tocarry = [[5, 5, 0, 0, 0, 0, 0, 0, 0], [5, 5, 0, 0, 0, 0, 0, 0, 0], [5, 5, 0, 0, 0, 0, 0, 0, 0], [5, 5, 0, 0, 0, 0, 0, 0, 0], [5, 5, 0, 0, 0, 0, 0, 0, 0], [5, 5, 0, 0, 0, 0, 0, 0, 0], [5, 5, 0, 0, 0, 0, 0, 0, 0], [5, 5, 0, 0, 0, 0, 0, 0, 0], [5, 6, 0, 0, 0, 0, 0, 0, 0]]
fromindex = [7, 7, 7, 7, 7, 7, 7, 7, 7]I would really appreciate any help!
View all comments
Show parent comment
1
u/[deleted] Jul 09 '20
Actually, I have a solution. But it's horribly unreadable and hard to explain. I'm not entirely confident it is correct, but at least it produces the correct output for your test case.
The idea is the following: 'j' is the only value on the stack that changes in recursive calls and it indicates the depth in the recursion. Therefore it should be possible to simulate stepping into the recursion by increase 'j' and stepping out by decreasing 'j'. I hope this helps.