Recursion to loop using stack, very simple code

Hello,

I want to convert the following program into a non-recursive code using a stack and a loop:

1
2
3
4
5
6
7
void write(int n) {
    if (n>0) {
        write(n-1);
        cout << n << " ";
        write(n-1);
    }
}


And here is the code I am using but that currently does not work, and I do not know why:

1
2
3
4
5
6
7
8
9
10
11
stack<int> S;
S.push(n);
while (not S.empty()) {
    int k = S.top(); 
    S.pop()
    if (k>0) {
        S.push(k-1);
        cout<<k-1<<" ";
        S.push(k-1);
    }
}


It doesn't work and I have no idea how to simulate that recursion. I thought it was enough to push into the stack the equivalent recursive call.

thanks
Last edited on
I thought it was enough to push into the stack the equivalent recursive call.


Nope. Each time write() is called, it will call write(n-1), which will also call write(n-2), which calls write(n-3) etc etc. So simply pushing n-1 won't do the job... you'd need to push all of them.

What's more... the order you'd have to push them in incredibly weird. write(3) outputs this:


1 2 1 3 1 2 1


write(4) outputs this:

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1



Honestly... given how freaking weird this function is... I really don't see a straightforward way to remove the recursion.
Thanks a lot for your help anyways :)
Topic archived. No new replies allowed.