Recursion to loop using stack, very simple code

[Nebur]

Hello,

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

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:

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

[Disch]

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.

[Nebur]

Thanks a lot for your help anyways :)