Iteration and recursion
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 27

Thread: Iteration and recursion

  1. #1
    Join Date
    Dec 2010
    Posts
    11

    Iteration and recursion

    Hi,

    I have to write a code with a iteration paradigm or with a recursion paradigm. I think that the first one is the best for performance even if it require more lines of code. But I don't know if I'm able to write a code that uses it.

    I have a vector of variables and so I know its dimension. For every variable I have to do a loop. Each loop must be nested inside the previous one. I have to create the loop on the fly because I don't know the dimension of the vector at compile time i.e. the vector can have different dimension. How can I do it?

    For instance

    (vector [x,y,z] ->
    for(x) {
    for (y) {
    for (z) { }
    }
    })

    The language is C++

  2. #2
    Join Date
    Mar 2011
    Posts
    46

    Re: Iteration and recursion

    pass in the x,y,z sizes on the interface and generally you roll down and in

    Code:
    void SortVectors(  vector [x,y,z],   unsigned short xsize, unsigned short ysize, unsigned short zsize){
    unsigned short x, y, z;
     
    for (z = 0; z < zsize; z++) {
        for  (y = 0; y < ysize; y++) {
            for (x = 0; x < xsize; x++) {
                 // do whatever with  vector[x,y,z] 
           }
        }
    };

  3. #3
    Join Date
    Dec 2010
    Posts
    11

    Re: Iteration and recursion

    I'm sorry if my explanation is not good enough. I have to make an arbitrary number of nested loops. I would like to know if the only way is the recursion paradigm.

  4. #4
    Join Date
    Mar 2011
    Posts
    46

    Re: Iteration and recursion

    Perhaps you need to explain what you are trying to do there are any number of ways to recurse and all have pro's and con's

    perhaps the simplist recursion is the factorial recurse

    Code:
    unsigned int factorial  (unsigned int a)
     {
       if (a == 1) return 1;
           else {
               a *= factorial(a-1);
              return a;
           }
     };
    if you plug in a value the procedure calls itself over and over recursing downwards

    Look at entering 4 in the above it loops thru itself 4 times

    result = factorial(4) * factorial(3) *factoria(2) * factorial(1);

    The function basically calls itself with its current value-1

    Normal sorting is another example but usually we use something like quicksort which is a divid and conquer rather than a full blind manual recursion because of speed.

  5. #5
    Join Date
    Mar 2011
    Posts
    46

    Re: Iteration and recursion

    Extendending from the previous post what would a quick sort of vertex3D look like ..

    Code:
    /*-COORD_TYPE----------------------------------------------------------------
      Units your 3d vertex points are in typically shorts, ints, or doubles.
     ---------------------------------------------------------------------------*/
    typedef double COORD_TYPE;					// For our example we are using doubles
    
    /*-VERTEX3D------------------------------------------------------------------
      3D vertix record structure defined
     ---------------------------------------------------------------------------*/
    typedef struct Vertex3D {
    	COORD_TYPE x;							// Vertex x co-ord
    	COORD_TYPE y;							// Vertex y co-ord
    	COORD_TYPE z;							// Vertex z co-ord
    } VERTEX3D, *PVERTEX3D;
    
    /*-Vswap3D---------------------------------------------------------------------
     Swaps the two given 3D vertexes around v1 and v2 
     ----------------------------------------------------------------------------*/
    static void Vswap3D (PVERTEX3D* v1, PVERTEX3D *v2){  
    	PVERTEX3D Temp;  
    
    	Temp = *v1;														// Hold current v1 vertex
    	*v1 = *v2;														// Transfer v2 to v1
    	*v2 = Temp;														// Set v2 to the held old v1 value
    };
    
    /*-partition3D_with_random------------------------------------------------------
     Partitions the 3D vertex array with randomness 
     ----------------------------------------------------------------------------*/
    static short partition3D_with_random(PVERTEX3D list[], short l, short h){
        short i;
        short p;			/* pivot element index */
        short firsthigh;	/* divider position for pivot element */
    
        p = l + (short)(rand() &#37; (int)(h - l + 1));						// Random partition point
        Vswap3D(&list[p], &list[h]);									// Swap the values
        firsthigh = l;													// Hold first high value
        for (i = l; i < h; i++)
    
            // This is what we are sorting based on 
            // .. the following line we are sorting based on vertex x value
           if(list[i]->x < list[h]->x) {								// Value at i is less than h
              Vswap3D(&list[i], &list[firsthigh]);					// So swap the value
                firsthigh++;											// Incement first high
            }
         Vswap3D(&list[h], &list[firsthigh]);							// Swap h and first high values
        return(firsthigh);												// Return first high
    }
    
    /*-quicksort3D_random---------------------------------------------------------
     Quick sort 3D veretex with random partition 
     ----------------------------------------------------------------------------*/
    static void quicksort3D_random(PVERTEX3D list[], short l, short h){
        short p;			/* index of partition */ 
    
        if ((h - l) > 0) {
            p = partition3D_with_random(list, l, h);					// Partition list 
            quicksort3D_random(list, l, p - 1);							// Sort lower partion
            quicksort3D_random(list, p + 1, h);							// Sort upper partition
        };
    };

    The code itself is remarkable simple it partitions a list and sorts by calling iteself over and over.

    The key two the code is we have a swap routine that swaps two vertex points.
    The key to what we are sorting is given by the one line

    // This is what we are sorting based on
    // .. the following line we are sorting based on vertex x value
    if(list[i]->x < list[h]->x)

    As you can see the simple test above is based on just the x value of two vertexes so the sort will be done so the vertexes in the array will come out smallest x to largest x

    You could have sorted on a euclidean distance for example based on some distance from point (P)

    Code:
    /*-Distance3D----------------------------------------------------------------
      Return euclidian distance between the two vertex3D points
     -------------------------------------------------------------------------------*/
    double Distance3D(PVERTEX3D v1,  PVERTEX3D v2){
        double dx, dy, dz;
    
        dx = v2->x - v1->x;            // Diff x
        dy = v2->y - v1->y;            // Diff y
        dz = v2->z - v1->z;            // Diff z
    
         if ((dx == 0.0)  &&  (dy == 0.0) && (dz==0.0))   // If diff's are zero
    	return (0.0); 		               // Distance is zero			
         return (sqrt(dx*dx + dy*dy + dz*dz));              // Calculate the 3D distance
    };
    
    // Now if we change the sort equality test to
    
         if(  Distance3D(list[i], P) <   Distance3D(list[h], P))
    What we will get is a sort of the array of vertexes based upon that which is closest to point P


    Is that the sort of thing you are looking for?
    Last edited by Uglybb; March 16th, 2011 at 09:23 AM.

  6. #6
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,888

    Re: Iteration and recursion

    Quote Originally Posted by erotavlas View Post
    I'm sorry if my explanation is not good enough. I have to make an arbitrary number of nested loops. I would like to know if the only way is the recursion paradigm.
    Recursion is never the only way. However, sometimes it may be the clearest.

    When you use recursion, you're effectively using the runtime stack to maintain some state for you. If you want, you can create a stack explicitly for this purpose without using recursion.

  7. #7
    Join Date
    Dec 2010
    Posts
    11

    Re: Iteration and recursion

    Thank you for the answers.
    I have read this article http://www.codeguru.com/cpp/cpp/algo...nt.php/c15111/ and now I think that first I will make a recursive version of the my algorithm and after I will try to convert it in compile time version (template form) to improve the performance.
    As I said in the previous post, I have to scan a vector of variables v = [x,y,z] and for each variable I have to do a for loop. The number of nested loops are equal to the number of the variables. Inside the innermost loop I have to make some operation. A snippet of my algorithm is the following.

    Code:
    void Recurse(const vector<string>& variablesVector)
    {
        // terminate recursion
        if (variablesVector.size() == 0)
        {
            // do some operations
    	    return;
        }
    
    	// loop for the variable in the data	
        for ()
    	{
         	
    	// recursive step - remove the front variable
            Recurse(variablesVector.erase(variablesVector.begin(), variablesVector.begin()+1));
    	}
    }
    
    void Do(const vector<string>& variablesVector)
    {
        Recurse(variablesVector);
    }
    Is this code doing the arbitrary nested loops as I want?

  8. #8
    Join Date
    May 2009
    Posts
    2,413

    Re: Iteration and recursion

    ---
    Last edited by nuzzle; March 18th, 2011 at 11:06 AM.

  9. #9
    Join Date
    Dec 2010
    Posts
    11

    Re: Iteration and recursion

    I don't understand your problem and I doubt anyone else does too.

    Lets assume you have exactly 3 "dimensions" known at compiletime. What would an iterative solution look like?
    I repeat again that I don't know the dimension at compile time. If I knew the dimension I would make a sufficient number of nested loops. I have a vector of variables and its dimension is only known at runtime.

    I would like to rewrite my recursive algorithm into the template version as specified here http://www.codeguru.com/cpp/cpp/algo...nt.php/c15111/, but this is a secondary problem related only to the performance.

    Removing elements at the front of a vector is expensive and should be avoided. If you need to do this use a queue instead.
    The vector is not so big, it will be in worst case about 50 elements.

  10. #10
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,888

    Re: Iteration and recursion

    Quote Originally Posted by erotavlas View Post
    The vector is not so big, it will be in worst case about 50 elements.
    The admonition against removing elements from the front stands. You should test a std::deque which has a pop_front() and push_front() function but otherwise an essentially identical interface to std::vector, and see if you get better performance with that.

  11. #11
    Join Date
    May 2009
    Posts
    2,413

    Re: Iteration and recursion

    Quote Originally Posted by erotavlas View Post
    I repeat again
    There's no use in repeating yourself because it doesn't become any clearer exactly what your problem looks like. If you want help I suggest you instead present an iterative solution to your problem with a fixed "dimension" say 3. You don't have to put in any detailed calculations but the structure of the algorithm must be visible.

    In principle it's very easy to turn a fixed number of nested loops into a variable number of nested loops using recursion. The recursive method performs one loop which is then called recursively down to the wanted neesting depth. But as I said, it's not very clear what your problem looks like.

    Also note that you cannot use templates if you don't know the "dimension" at compiletime. Templates will allow you to parametrize the number of nested loops but you still have to decide how many loops you want at compiletime.

    Finally if you don't have to remove elements from the vector in the iterative solution you don't have to do it in the recursive.

    The vector is not so big, it will be in worst case about 50 elements.
    If this means your algorithm is going to have up to 50 nested loops then it's highly likely you're approaching the problem from the wrong angle. Even if the loops go from 0 to 1 only the innermost loop will run 2^50 times which is 10^15 approximately. Your program will run for years.
    Last edited by nuzzle; March 18th, 2011 at 02:01 PM.

  12. #12
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,010

    Re: Iteration and recursion

    Quote Originally Posted by erotavlas View Post
    I have read this article http://www.codeguru.com/cpp/cpp/algo...nt.php/c15111/ and now I think that first I will make a recursive version of the my algorithm and after I will try to convert it in compile time version (template form) to improve the performance.
    See nuzzles remark about compile vs run time. The only way you can use templates would be to generate code for a set of possible recursion depths (e.g. from 1 to 50), which is likely to cause huge amounts of code bloat. I doubt this is worth the performance gain (if it would achieve any gain at all).
    Quote Originally Posted by erotavlas View Post
    Code:
    void Recurse(const vector<string>& variablesVector)
    {
        // terminate recursion
        if (variablesVector.size() == 0)
        {
            // do some operations
    	    return;
        }
    
    	// loop for the variable in the data	
        for ()
    	{
         	
    	// recursive step - remove the front variable
            Recurse(variablesVector.erase(variablesVector.begin(), variablesVector.begin()+1));
    	}
    }
    
    void Do(const vector<string>& variablesVector)
    {
        Recurse(variablesVector);
    }
    Is this code doing the arbitrary nested loops as I want?
    The code no, because it won't compile. But the structure/algorithm looks ok to me. Note that you need to copy the function argument (or pass it by value) if you want to modify it. In the recursive call, you could also pass a temporary vector created using vector's range constructor (as an alternative to erasing the front element). Yet another possibility would be to pass a 'depth' index together with the vector, such that you only adjust the index and not the vector in the recursive calls.

    What's not clear from your description is how you actually iterate. All your for loops are basically empty. How do you intend to store the 'indices' for each variable in the current iteration? Globally?
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  13. #13
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,699

    Re: Iteration and recursion

    If you need an unknown number of nested loops at runtime then this is worth a look.

    http://drdobbs.com/cpp/184403251
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

  14. #14
    Join Date
    Dec 2010
    Posts
    11

    Re: Iteration and recursion

    Quote Originally Posted by JohnW@Wessex View Post
    If you need an unknown number of nested loops at runtime then this is worth a look.

    http://drdobbs.com/cpp/184403251
    Thank you for your answer. It's an other way to implement what I want.

  15. #15
    Join Date
    Dec 2010
    Posts
    11

    Re: Iteration and recursion

    Quote Originally Posted by D_Drmmr View Post
    See nuzzles remark about compile vs run time. The only way you can use templates would be to generate code for a set of possible recursion depths (e.g. from 1 to 50), which is likely to cause huge amounts of code bloat. I doubt this is worth the performance gain (if it would achieve any gain at all).

    The code no, because it won't compile. But the structure/algorithm looks ok to me. Note that you need to copy the function argument (or pass it by value) if you want to modify it. In the recursive call, you could also pass a temporary vector created using vector's range constructor (as an alternative to erasing the front element). Yet another possibility would be to pass a 'depth' index together with the vector, such that you only adjust the index and not the vector in the recursive calls.

    What's not clear from your description is how you actually iterate. All your for loops are basically empty. How do you intend to store the 'indices' for each variable in the current iteration? Globally?
    In the last two weeks I have thought a lot about the my problem. This is my code with some adjustments

    Code:
    void Recurse(const vector<string>& variablesVector, Data* data)
    {
        // terminate recursion
        if (variablesVector.size() == 0)
        {
            // do some operations with the data
    
    	    return;
        }
    
    	// loop for the variable in the data	
        for (Data::const_iterator it = data->begin(); it != data->end(); ++it)
    	{
         	
    	// recursive step - remove the front variable for the next iteration
            Recurse(variablesVector.erase(variablesVector.begin(), variablesVector.begin()+1), &data);
    	}
    }
    My code does the following operations. Given the vector of the variables and the Data (domain of the variables), it takes the first variable, search inside the domain of values Data and executes the recursive step. Takes the second variable, search inside the domain of values Data and executes the recursive step and so on.
    At last step when there are no any variable in the vector, the code executes some operations on the data (each data for each variable).
    I think that it realizes the behaviour of nested loops.
    Code:
    Example:
    For x For y For z -> variablesVector[x,y,z]
    Domain for each variable -> Data
    for x in subset(Data)
       for y in subset(Data)
          for z in subset (Data)
            do (x,y,z)
    Now I know that the complexity can be intractable with only small number of variables and small number of different values for each variable.
    You are right, I can't use the template version if I don't know at compile time the number of variables in the vector. My vector is read from a parser, and so I don't know it before run time. Do you have a suggestions about how can I do to reduce the complexity of huge number of recursive calls?

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center