Recursion using Stack

[chandra.somesh]

I recently was having trouble converting implementaion of recursions
using stack.
While single level of recursions are quite intuitive , it is when we
have more than one recursive calls in the function that the problem
arises.Consider for example a simple postorder traversal

void post(struct node * p)
{
if(p==NULL)
return;

post(p->left);
post(p->right);

cout<<p->info;

return;
}


if i try to implement the above code using stacks then this is how i
approach it.....

void post(sturct node *p)
{

do{
while(p!=NULL){
push(p);
p=p->left;
}
\\The above code signifies the first line of recursion
post(p->left);

p=pop(); \\Since p was null in previous step ,warranting the
pop in
the stack.

push(p); \\While this is to signify post(p->right);
p=p->right;

if(p==NULL)
{
p=pop();
cout<<p->info;
p=pop();
}
}while(!empty(queue));
}

Now the last few lines i really got confused and hence the resulting
code doesn't implement the correct logic.

Where am i going wrong?is there a thumb rule that one could follow in
order to implemnt recursions(of any level) using stacks.

Thanks in advance

Somesh

 

[Gianni Mariani]

I recently was having trouble converting implementaion of recursions
using stack.
While single level of recursions are quite intuitive , it is when we
have more than one recursive calls in the function that the problem
arises.Consider for example a simple postorder traversal

void post(struct node * p)
{
if(p==NULL)
return;

post(p->left);
post(p->right);

cout<<p->info;

return;
} ....

Where am i going wrong?is there a thumb rule that one could follow in
order to implemnt recursions(of any level) using stacks.

You need to push various state that indicates all the levels of
processing. See below struct stack_frame.

#include <string>
#include <iostream>
#include <list>

struct node
{
node * left;
node * right;
std::string info;

node( node * i_left = 0, node * i_right = 0, const std::string &
i_info )
: left( i_left ),
right( i_right ),
info( i_info )
{
}
};

void post( node * p )
{
if(p==NULL)
return;

post(p->left);
post(p->right);

std::cout<<p->info;

return;
}

struct stack_frame
{
node * m_p;
enum State {
ProcessLeft,
ProcessRight,
Done
};

State m_state;

stack_frame( node * i_p )
: m_p( i_p ),
m_state( ProcessLeft )
{
}
};

void nr_post( node * p )
{
std::list< stack_frame > list;

if ( p == NULL )
{
return;
}

list.push_front( stack_frame( p ) );

while ( ! list.empty() )
{
stack_frame & frame = list.front();

if ( ! frame.m_p )
{
list.pop_front();
}
else
{

switch ( frame.m_state )
{
case stack_frame:rocessLeft :
{
list.push_front( stack_frame( frame.m_p->left ) );
frame.m_state = stack_frame:rocessRight;
break;
}

case stack_frame:rocessRight :
{
list.push_front( stack_frame( frame.m_p->right ) );
frame.m_state = stack_frame:one;
break;
}
case stack_frame:one :
{
std::cout << frame.m_p->info;
list.pop_front();
break;
}
}
}
}
}


int main()
{
node * a =
new node(
new node(
0,
new node( 0, 0, "1" ),
"2"
),
new node( 0, 0, "3" ),
"4"
);

std::cout << "recursive :";
post( a );
std::cout << "\nnon-recursive :";
nr_post( a );
std::cout << "\n";

}

 

[Mark P]

I recently was having trouble converting implementaion of recursions
using stack.
While single level of recursions are quite intuitive , it is when we
have more than one recursive calls in the function that the problem
arises.Consider for example a simple postorder traversal...

If you read a book on algorithms like CLR you'll see that depth-first
search involves looking at each node twice. (As I recall, CLR calls
this something like "pre-visit" and "post-visit".) The idea is that the
first time you visit a node you push it onto the stack and the second
time you pop it off the stack. Conceptually, you encounter a node in a
tree (visit one), then you go down and visit all of its children and
later you come back and finish with that node (visit two). The point is
that you need some way to know whether you've previously visited a node
or not. The easiest way to do this is to have some sort of marker that
you can set in each node.

Here's an example (I haven't actually compiled this code so this should
not be used in mission-critical applications):

struct node
{
node* left;
node* right;
int val; // I'll suppose the nodes hold ints
bool marked; // initially false for all nodes
};

Let's take for granted that we have an empty stack of node* that
supports the usual operations: push, pop, and top.

void DFS(node* p)
{
stack.push(p); // this starts the DFS on p
while (!stack.empty())
{
node* top = stack.top();
if (!top->marked) // first time visiting this node
{ // so process its children first
top->marked = true; // reminder that we've seen this node
if (top->right)
stack.push(top->right);
if (top->left)
stack.push(top->left);
}
else // second visit - children already processed
{
std::cout << top->val << std::endl;
stack.pop(); // we're done with this node & its children
}
}
}

And that's all there is to it.

- Mark

 

[Ajay]

Do we really need a marker.. (Am not trying the full code.. just
writing an algo)..

Put the root node on a stack;
while (stack is not empty) {
remove a node from the stack; //cout<<p->info

put all NON_NULL children of node onto the stack;
//push(p->right);push(p->left)
}

 

[Mark P]

Do we really need a marker.. (Am not trying the full code.. just
writing an algo)..

Put the root node on a stack;
while (stack is not empty) {
remove a node from the stack; //cout<<p->info

put all NON_NULL children of node onto the stack;
//push(p->right);push(p->left)
}

That is, as you say, an algorithm, but it doesn't do the same thing.
Yours evaluates the parent before evaluating any of its children. I'm a
bit rusty on this, but I think that's called a pre-order traversal. The
OP's question about recursion would typically involve a post-order
traversal-- children evaluated before parent. In this case, a marker is
at least an easier way if not the only way.