recursion into loop

This is a discussion on recursion into loop within the C++ Programming forums, part of the General Programming Boards category; Hi, I am trying to compute the strongly connected components of a graph. I have my recursive program, but due ...

  1. #1
    Registered User
    Join Date
    Jun 2006
    Posts
    28

    recursion into loop

    Hi,

    I am trying to compute the strongly connected components of a graph. I have my recursive program, but due to stack overflow problem, I want to turn it into an iterative one. However, I am running into some problems with the iterative one.

    I'd appreciate some help. Here is my code of the recursive one, and my attempt to make into a loop, which is not working.

    thanks

    Code:
    /* Recursive one*/
    
    typedef unsigned int vType
    
    #define REPEAT do{
    #define UNTIL( condition ) }while(!(condition));
    
    enum cases {finished, live, unexplored}; 
    
    unsigned int component;
    
    void scc_djikstra(Graph &g, vType &v, vType &c, 
                      std::stack<vType> &S, std::stack<vType> &C, 
                      std::vector<vType> &number, std::vector<cases> &status){
    	vType c_prime, w;
    	
    	c++;
    	status[v] = live;	
    	number[v] = c; 
    	S.push(v);
    	C.push(c);
    	
    	std::list< E >::const_iterator itr;	
    	// iterate through out-edges (v,w) of v
    
    	for(itr = g[v].second.begin(); itr != g[v].second.end(); ++itr)	{	   	
    		w = (*itr).first;    
    		if (status[w] == unexplored)
                          scc_djikstra(g, w, c, S, C, number, status);
    		else {
    			if (status[w] == live){
    				REPEAT
    					c_prime = C.top();
    					C.pop();					
    				UNTIL (c_prime <= number[w])
    				C.push(c_prime);
    			}			
    
    		}// else
    	}// for
    	c_prime = C.top();
    	C.pop();
    
    	if (number[v] == c_prime){
    
    		REPEAT
    			w = S.top();
    			S.pop();					
    			status[w] = finished;
                            number[w] = v;
    		UNTIL (w == v)	
    	}
    	else
    		C.push(c_prime);				
    }
    
    //......
    /*
    g is the graph in adjacency list representation.
    
    g is a vector, where each element is std::pair<unsigned int, std::list> .... <node, out-edges-list>
    
    and each element in the list is of type std::pair< vertexType, weightType >
    
    */
    // call function
    
    std::stack<vType> *S = new std::stack<vType>();
    std::stack<vType> *C = new std::stack<vType>();
      
    std::vector<vType> *number = new std::vector<vType>(g.nV(), 0);
    std::vector<cases> *status = new std::vector<cases>(g.nV(), unexplored);		
      
    for (vType i = 0; i < g.nV(); ++i){
      if ( (*status)[i] == unexplored )
        scc_djikstra(g, i, h, components);
    }		
    
    number->clear();  delete number;
    status->clear();  delete status;
      
    delete S;
    delete C;

    Code:
    /* iterative one*/
    void scc_djikstra_iterative(Graph &g){
    
      vType c = 0;
      vType v, w, c_prime;
      std::stack<vType> S;
      std::stack<vType> C;
      
      std::vector<vType> number(g.nV(), 0);
      std::vector<cases> status(g.nV(), unexplored);	
      
      EdgeList::const_iterator start, end;
      
      std::stack<vType, std::vector<vType> > verticesStack;  // vertices to be visited
      
      // visit all vertices
      for (vType i = 0; i < g.nV(); ++i){
        
        if ( status[i] == unexplored )          
          verticesStack.push(i);          // store on stack for further processing
    
        
        // process stack
        while(!verticesStack.empty()) {
          
          v = verticesStack.top();
          verticesStack.pop();
          
          c++;
          status[v] = live;
          number[v] = c;
          S.push(v);
          C.push(c);
       
           
          // iterate through the out-edges of v
          start  = g[v].second.begin();
          end    = g[v].second.end();
          
          while(start != end) {
            --end;
            w = (*end).first;
            if (status[w] == unexplored)          
              verticesStack.push(w);       // store on stack for further processing
            
            else {
              
              if (status[w] == live){
                REPEAT
                  c_prime = C.top();
                  C.pop();		
                UNTIL (c_prime <= number[w])
                
                C.push(c_prime);
              }
                     
              c_prime = C.top();
              C.pop();
              if (number[v] == c_prime){
    
                REPEAT
                  w = S.top();
                  S.pop();          
                  status[w] = finished;
                  number[w] = v;    
                UNTIL (w == v)
    
              }
              else 
                C.push(c_prime);				
              
            } // else      
         
          } // while (start!=end)      
    
        }  // while !verticesStack.empty()
        
      } // for i
      
      std::cerr<<"\nNumbers: \n";
      std::copy(number.begin(), number.end(), std::ostream_iterator<unsigned int> (std::cerr, " "));  
    }

  2. #2
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    I am not really going to delve too much into your actual code, rather I will offer a suggestion that would allow you to keep your code recursive (or even alter it into a loop... whatever you like better).

    Why not have your "unexplored" data be stored in its own vector, and then process your entire memory block, then process your "unexplored" data, then merge all your data into one vector (or binary tree or whatever).

  3. #3
    Registered User
    Join Date
    Jun 2006
    Posts
    28
    thanks for the reply,

    however, I'd really like to learn how to translate the recursive code into an iterative one in a more traditional way. Is something that is bugging me

    I'd appreciate the help with this.

    thanks

  4. #4
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,783
    Problem is, they're two different things. Some things are suitable for recursion, some for iteration. Sometimes it just isn't feasible to turn something recursive into iterating.
    To keep the function recursive, you can try putting all arguments into a struct and passing a pointer to the struct to lessen the memory print for each recursion. You can also put temporary variables used by the function inside such a struct to save more memory.

    Good luck.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  5. #5
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,249
    Recursion can be transformed cleanly to iteration if the recursion is not multiple. In other words, this:

    Code:
    void recur()
    {
        ...
        recur();
        ...
    }
    Is easy to convert, whereas this is harder:

    Code:
    void recur()
    {
        ...
        recur();
        ...
        recur();
        ...
    }
    The reason being, you can convert singular recursion to iteration by packing all local variables into a struct, putting these on a stack, and replacing the recursive call by a loop. But if the recursion is multiple, you have to have a way of saving where the "recursion" came from, so that on each iteration you can restart the loop from the right place, and so you end up with either a bunch of goto statements or a very weird looking switch. At that point it's probably better to use real recursion.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. My loop within loop won't work
    By Ayreon in forum C Programming
    Replies: 3
    Last Post: 03-18-2009, 10:44 AM
  2. Personal Program that is making me go wtf?
    By Submeg in forum C Programming
    Replies: 20
    Last Post: 06-27-2006, 12:13 AM
  3. A somewhat bizzare problem!!! - WHILE LOOP
    By bobthebullet990 in forum C Programming
    Replies: 3
    Last Post: 03-31-2006, 06:19 AM
  4. when a while loop will stop ?
    By blue_gene in forum C Programming
    Replies: 13
    Last Post: 04-20-2004, 03:45 PM
  5. replacing a loop with recursion
    By linucksrox in forum C Programming
    Replies: 2
    Last Post: 04-14-2004, 07:27 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21