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?

Where would you start? What have you tried, and why are you having problems? — Mahmoud Al-Qudsi
– Mahmoud Al-Qudsi, Commented Sep 30, 2011 at 10:08
General question: "how do I replace recursion with iteration?" answer "use a stack data structure". Sometimes there are simpler answers than this (e.g. using a loop instead of recursion), but it depends on the complexity of the problem. — Merlyn Morgan-Graham
– Merlyn Morgan-Graham, Commented Sep 30, 2011 at 10:57

GreenScape · Accepted Answer · 2011-09-30 10:54:26Z

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

looks like you forgot 'continue' at the end of the 1st 'if' statement.

Alexey Frunze · Accepted Answer · 2011-09-30 10:15:44Z

1

Have an empty vector/array/queue of CvSeq*'s. Have an index/pointer into it, at first pointing to its beginning (where the very first element will be).

Start with the tree's root and add its h_next and v_next to the vector.

Then while the index is less than the number of pointers in the vector - 1, take vector[index]'s h_next and v_next, add them at the end of the vector and do ++index.

You end up with pointers to all tree nodes in that vector/array/whatever.

Then you just iterate over it, painting things and whatnot.

answered Sep 30, 2011 at 10:15

Alexey Frunze

62.4k14 gold badges90 silver badges190 bronze badges

3 Comments

Alexey Frunze Over a year ago

@MahmoudAl-Qudsi: Conceptually it's easy, but yes, there's a better way to do this.

Mahmoud Al-Qudsi Over a year ago

If I had more info about cvesq it would be easier to go on... but regardless, the most compact way would be to either use pre-existing or else add h_prevous and v_previous, then iterate to the end and walk backwards without having to store a single thing.

Konstantin Oznobihin Over a year ago

@Mahmoud Al-Qudsi: it's a tree, what sense would make h_previous and v_previous members to it? Are supposing to store necessary information in nodes themselves instead of a separate stack?

Collectives™ on Stack Overflow

Refactor recursive algorithm into an iterative one?

2 Answers 2

1 Comment

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related