stop a recursion

• 10-30-2006
acosgaya
stop a recursion
hi,
I am implementing an algorithm, but I am having problems stopping my recursion. Basically, my procedure partitions a set of d-dimensional points (stored in a vector of vectors) according to the median in a given dimension, it performs some computation, and returns a value.

The problem I have is that sometimes the criteria (the median in this case) which partitions my set into 2 parts, will yield one part which is empty, and then I cannot stop my recursion. (This happens for example when all the values along one dimension are equal and therefore they should go to one partition leaving the other one empty)

Here is a part of my code.
Code:

```vector < vector <int> >  SkylineBasic(vector < vector <int> > M, int dimension){           vector < vector <int> > S1, S2;         vector < vector <int> > vResult, vFilterResult;         if (M.size()==1){                 return M;         }         sort(M.begin(), M.end(), vec_less(dimension));                 int pivot = M[M.size()/2][dimension];         vector < vector <int> >::iterator medianIter = stable_partition (M.begin(), M.end(), vec_part(dimension, pivot));    //bind2nd( vec_less(dimension), 7)                   vector < vector <int> > P1(M.begin(), medianIter);         vector < vector <int> > P2(medianIter++, M.end());                 S1 = SkylineBasic(P1, dimension);          S2 = SkylineBasic(P2, dimension);                 vResult = S1;                        vFilterResult = MergeBasic(S1, S2, dimension);  // do some work with both sets               //then, the union of S1 with the result of the previous work         vResult.insert(vResult.end(), vFilterResult.begin(), vFilterResult.end());                                                        return vResult; }```
I would appreciate some help, as how to stop the recursion when this case of having one empty part, happens.
• 10-30-2006
Daved
Can't you just return when the vector is empty like you do when it has a size of one?
• 10-30-2006
acosgaya
I tried, but it does not stop
Code:

```        if (M.size()<=1){                                 return M;                         }```
• 10-30-2006
Xeridanus
if you are ending up with empty partitions, just write a function to test if a partition is empty, then add another stopping case. i haven't done anything with vectors so they might have their own for doing just that.
• 10-30-2006
Daved
Ok, the problem is that when you have a certain set of values, your partitions have 0 items in one partition and multiple items in the other because all the elements are equal, right? Then you need to check both partitions P1 and P2 before you call SkylineBasic again. If either are empty, then don't call the function for either one, otherwise you will keep getting the same partitioning and never break down the vector with points in it.
• 10-31-2006
acosgaya
Hi,
It seems that now with the added condition to my procedure, the recursion stops properly.
But now I have a similar problem in another recursion inside MergeBasic. I have written my code below.
Note: it is ok to have one empty partition, for example, in the case that the elements along one dimension are equal,
that is why I should not use this following code, becase it might make that points (vectors) that correspond to say set S1, end up in set S2.
Code:

```vector < vector <int> >::iterator medianIter = stable_partition (M.begin(), M.end(), vec_part(dimension, pivot)); if (medianIter==M.begin() || medianIter==M.end())     medianIter=M.begin()+M.size()/2;```
In this case I try to partition around the median.

Btw, the scenario is the following:
Having a set of objects S in an n-dimensional space D=(D1, …, Dn)
Point u dominates Point v (u and v belong to S) if (u.Di <= v.Di) for 1 <= i <= n, and on at least one dimension Dj, u.Dj < v.Dj
u is a skyline object if u is not dominated by any other objects in S
Code:

```/*******************************************************************************************  * SkylineBasic:  *        equipartitions the set into two parts, then, recursively applies the whole algorithm  *        to both parts, obtains two sets of their respective Skyline, and combines the results.  *******************************************************************************************/ vector < vector <int> >  SkylineBasic(vector < vector <int> > M, int dimension){           vector < vector <int> > S1, S2;         vector < vector <int> > vResult, vFilterResult;         if (M.size()==1) // partitioning stops                        return M;                   // calculate an approximate median         sort(M.begin(), M.end(), vec_less(dimension));                int pivot =  M[M.size()/2][dimension];         vector < vector <int> >::iterator medianIter = stable_partition (M.begin(), M.end(), vec_part(dimension, pivot));                   // equipartition the set         vector < vector <int> > P1(M.begin(), medianIter);         vector < vector <int> > P2(medianIter, M.end());                 if ( (P1.size()>0) && (P2.size()>0) ) {  <=== new condition to avoid enter again                 // computes the skyline recursively           S1 = SkylineBasic(P1, dimension);                            S2 = SkylineBasic(P2, dimension);                        }         else{                 S1 = P1;                                                S2 = P2;                                        }                 //"filters" the elements from S2, that are dominated by elements in S1         //None of the points in S1 can be dominated by a point in S2                        vResult = S1;                                if (S2.size()>0){        // is S2 is not empty                 if (S1.size()==0)        // and if S1 is empty                         vFilterResult = S2; // the result is just S2 (none of S2 is dominated by S1, because S1 is empty)                 else                         vFilterResult = MergeBasic(S1, S2, dimension); // if both S1 and S2 are not empty, then enter into MergeBasic         }         vResult.insert(vResult.end(), vFilterResult.begin(), vFilterResult.end());        //get rid of this                                                 return vResult; }```
Here in MergeBasic, for example I have the following situation where the recursion never stops:
using dimension 5 (the 5th elements of each vector)
S1:
45 2 16 41 31 6
42 4 44 48 31 6

S2:
50 14 3 34 42 11
41 16 9 10 38 11
29 20 1 5 43 12

==> pivot: 31
partition S1 around 31
S11: (empty)

S12:
45 2 16 41 31 6
42 4 44 48 31 6
partition S2 around 31

S21:

S22:
50 14 3 34 42 11
41 16 9 10 38 11
29 20 1 5 43 12

the of course when it enters into this line
R2 = MergeBasic(S12, S22, dimension);
it never stops.
Code:

```/*******************************************************************************************  * filter:  *        computes the filter(S1|S2), which determines the elements of the set S2 which are not  *        dominated by any element in set S1.  *******************************************************************************************/ vector< vector <int> > MergeBasic(vector< vector <int> > S1, vector< vector <int> > S2, int dimension){         vector< vector <int> >                 A, S11, S12, S21, S22, vTmp;         vector< vector <int> >                 R, R1, R2, R3, intersct;                        vector< vector <int> >::iterator                 vIter;         vector <int>                 q, p;         vector< vector <int> >::iterator                 medianIter;                                        unsigned int                 i;                         if (S1.size()==1){  // trivial case                 p = S1[0];                 for (i=0; i<S2.size(); i++){                         if ( domination(p, S2[i], D) != 2 ) //if p does not dominate q                                 R.push_back(S2[i]);                                        }                 return R;                        }          if (S2.size()==1){  // trivial case           R = S2;           q = S2[0];           for (i=0; i<S1.size(); i++){                   p = S1[i];                   if (domination(p, q, D)== 2) { // if p dominates q                           R.clear();                           break;                   }           }                 return R;                                  }         if (dimension == 1){        // dimension is low                 sort(S1.begin(), S1.end(), vec_less(0));                 int min = S1[0][0];                 for (i=0; i<S2.size(); i++){                         if (S2[i][0] < min)                                 R.push_back(S2[i]);                 }                        return R;                                        }                // general case                                        else {                                                                        int pivot = 0;                 if (S1.size()>0)        {                         sort(S1.begin(), S1.end(), vec_less(dimension-1));                                                                                                                          pivot = S1[S1.size()/2][dimension-1];                //approximate median                         medianIter = stable_partition (S1.begin(), S1.end(), vec_part(dimension-1, pivot));                                                            S11.assign(S1.begin(), medianIter);                         S12.assign(medianIter, S1.end());                 }                 // partition S2 with the pivot used in S1                 medianIter = stable_partition (S2.begin(), S2.end(), vec_part(dimension-1, pivot));                         vector < vector <int> > S21(S2.begin(), medianIter);                 vector < vector <int> > S22(medianIter, S2.end());                                                //compare adjacent parts                                        R1 = MergeBasic(S11, S21, dimension);                 R2 = MergeBasic(S12, S22, dimension);                                //compare diagonally                                R3 = MergeBasic(S11, R2, dimension-1);                                 R = R1;                                         R.insert(R.end(), R3.begin(), R3.end());                 return R;         }                 }```
I would appreciate some suggestions about how to stop the recursion inside MergeBasic in this situations.

Thanks

p.s. this paper has the "basic divide and conquer" that I am trying to implement:
http://citeseer.ist.psu.edu/borzsonyi01skyline.html