stop a recursion

This is a discussion on stop a recursion within the C++ Programming forums, part of the General Programming Boards category; hi, I am implementing an algorithm, but I am having problems stopping my recursion. Basically, my procedure partitions a set ...

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

    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.

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,319
    Can't you just return when the vector is empty like you do when it has a size of one?

  3. #3
    Registered User
    Join Date
    Jun 2006
    Posts
    28
    I tried, but it does not stop
    Code:
     	if (M.size()<=1){
     		
    		return M;
     		
     	}

  4. #4
    Registered User Xeridanus's Avatar
    Join Date
    Oct 2006
    Location
    QLD, Aussieland
    Posts
    11
    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.

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    7,319
    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.

  6. #6
    Registered User
    Join Date
    Jun 2006
    Posts
    28
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 08:45 PM
  2. Recursion
    By jordan_230 in forum C Programming
    Replies: 0
    Last Post: 11-09-2008, 03:02 PM
  3. Recursion
    By Lionmane in forum C Programming
    Replies: 11
    Last Post: 06-04-2005, 12:00 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. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 09:56 AM

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