Refactor recursive algorithm into an iterative one?

Question

I have following recursive algorithm needed to redactor into iterative process. CvSeq is a tree structure.Where contour->h_next gives the next node in the same level. contour->v_next gives the next contour in level below.(child node)

void helperParseCurves(CvSeq* contour, int level) {

    if(contour->h_next != NULL) {
        helperParseCurves(contour->h_next, level);
    }
    if(contour->v_next != NULL) {
        helperParseCurves(contour->v_next, level+1);
    }

    //Process the nodes in contour
    for(int i=0; i<contour->total; i++){        
        CvPoint* p = CV_GET_SEQ_ELEM(CvPoint, contour, i);
        //Paint the point p
    }

}

I want to refactor this logic into iterative algorithm. Any tips on this?

Answer 1

To traverse nodes w/o recursion you will need stack for saving previous states. [Recursion is actually using of stack as well...] :

struct StackData
{
 CvSeq* contour;
 int level;
 int traversed;
};

const int traversed_l = (1 << 0);
const int traversed_r = (1 << 1);

const int stack_size = 50; // should be at leas max depth
StackData stack[stack_size];
int stack_p = 0;

void helperParseCurves(CvSeq* contour, int level) {

    int traversed = 0;

    while(contour)
    {
       if(contour->h_next != NULL && !(traversed & traversed_l)) { // down to left
        assert(stack_p < stack_size);                             // and save current state
        traversed |= traversed_l;
        stack[stack_p].contour = contour;
        stack[stack_p].level = level;
        stack[stack_p].traversed = traversed;
        ++stack_p;
        contour = contour->h_next;
        traversed = 0;
        continue;
        }

       if(contour->h_next != NULL  && !(traversed & traversed_r)) { // down to right
        assert(stack_p < stack_p);                             // and save current state
        traversed |= traversed_r;
        stack[stack_p].contour = contour;
        stack[stack_p].level = level;
        stack[stack_p].traversed = traversed;
        ++stack_p;
        contour = contour->v_next;
        level = level+1;
        traversed = 0;
        continue;
       }


       //Process the nodes in contour
       for(int i=0; i<contour->total; i++){      
            CvPoint* p = CV_GET_SEQ_ELEM(CvPoint, contour, i);
            //Paint the point p
       }

       // move up because either left and right nodes are NULL or already traversed
       if(!stack_p) break; // we are at the top
       contour = stack[stack_p].contour;
       level = stack[stack_p].level;
       traversed = stack[stack_p].traversed;
       --stack_p;
    }
}