Recursion to loop using a stack

Question

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<<" ";
        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

I need two push since there are 2 rec. calls on the write function, otherwise it will just write numbers from n to 1. — Ruben
– Ruben, Commented Oct 15, 2014 at 18:31
@DieterLücking there is double call in recursive so that not the problem — Slava
– Slava, Commented Oct 15, 2014 at 18:33
@Ruben your assumption is wrong, it would be equivalent if there is only one call — Slava
– Slava, Commented Oct 15, 2014 at 18:42

Slava · Accepted Answer · 2014-10-15 19:16:38Z

1

The problem is you do 2 pushes to the stack, but first write() is called recursively before the print with all call chain.

Here is iterative equivalent for your recursive calls:

std::stack<int> S;
for( int i = n; i > 0; --i )
   S.push( i );

while( not S.empty() ) {
    int k = S.top();
    S.pop();
    for( int i = k - 1; i > 0; --i ) {
        S.push( i );
    }
    std::cout << k << " ";
}

answered Oct 15, 2014 at 19:16

Slava

44.4k2 gold badges54 silver badges100 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Angew is no longer proud of SO · Accepted Answer · 2014-10-15 19:08:33Z

1

Your problem is that the first call to write(n - 1) happens before the output, but the evaluation of the popped value happens after it.

You can make your stack simulate actual activation records:

enum Action
{
  Call, Write
};

struct Record
{
  Action action;
  int arg;
};

stack<Record> S;
S.push({Call, n});
while (not S.empty()) {
  auto rec = S.top();
  S.pop()
  switch (rec.action) {
    case Call:
      if (rec.arg > 0) {
        S.push({Call, rec.arg - 1}); // corresponds to 2nd write() call
        S.push({Write, rec.arg});
        S.push({Call, rec.arg - 1}); // corresponds to 1st write() call
      }
      break;
    case Write:
      std::cout << rec.arg << ' ';
      break;
  }
}

answered Oct 15, 2014 at 19:08

Angew is no longer proud of SO

172k18 gold badges377 silver badges478 bronze badges

6 Comments

Ruben Over a year ago

So you make a distnction between when we have to write and when we have to push? In that case, you are never changing Rec.arg ?

Angew is no longer proud of SO Over a year ago

@Ruben Why should I change it? It's just a value read from the stack. It would be like changing the value of n in your original recursive function.

Ruben Over a year ago

nvm, just realised of the way you push :p

Ruben Over a year ago

So there is a variable that indicates what is needed to do. Provided there were more situations, let's say 3, would this variable have 3 values instead? And ofc the switch would change accordingly?

Angew is no longer proud of SO Over a year ago

@Ruben Yes, it would.

|

Collectives™ on Stack Overflow

Recursion to loop using a stack

2 Answers 2

Comments

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related