Iteration and recursion

[erotavlas]

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++

[Uglybb]

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

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] 
       }
    }
};

[erotavlas]

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.

[Uglybb]

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

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.

[Uglybb]

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

/*-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() % (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)

/*-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?

[Lindley]

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.

[erotavlas]

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.

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?

[nuzzle]

---

[erotavlas]

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.

[Lindley]

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:eque 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.

[nuzzle]

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.

[D_Drmmr]

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).

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?

[JohnW@Wessex]

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

http://drdobbs.com/cpp/184403251

[erotavlas]

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.

[erotavlas]

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

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.

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?