Recursive boolean function

Question

Say I have the following:

bool signal(QtreeNode * & orig, QtreeNode * & n, int tolerance) {

    bool signal1= false, signal2= false, signal3= false, signal4= false;
    if(n->isLeaf()){
        if(totalDiff>tolerance) //suppose these were defined
            return true;
        else return false;
    }
    signal1=signal(orig, n->neChild, tolerance); 
    signal2=signal(orig, n->nwChild, tolerance);
    signal3=signal(orig, n->swChild, tolerance);
    signal4=signal(orig, n->seChild, tolerance);

    if(signal1 || signal2 || signal3 || signal4)
        return true;
    else return false;
}

And say I call that method from some wrapper method like this:

signal1=signal(orig, n, tolerance);
    if(signal1)
        //do something

So what I'm doing here is traversing an entire quad-tree looking for just one case where I get true. All I need for this function to do is to return true in one case where totalDiff is greater than tolerance. I'm afraid that what I have isn't doing what I hoped it would do. Looking at function, does it seem like, when I set signal1 in my wrapper method, that I will get true back if it finds just 1 case of that condition? Or am I doing it wrong?

yan · Accepted Answer · 2011-03-30 04:54:37Z

The function looks correct, but I have a few stylistic comments. First, try to call it something else, signal is a very common function in POSIX operating systems.

Secondly, I'd either include actual function calls in an if statement or just have 4 if statements, each returning, to short circuit evaluation and to (subjectively) clean up the code a bit. That is, either:

return (signal(orig, n->neChild, tolerance) ||
        signal(orig, n->nwChild, tolerance) ||
        signal(orig, n->swChild, tolerance) ||
        signal(orig, n->seChild, tolerance));

or:

if (signal(orig, n->neChild, tolerance))
   return true;
if (signal(orig, n->nwChild, tolerance))
   return true;
if (signal(orig, n->swChild, tolerance))
   return true;
if (signal(orig, n->seChild, tolerance))
   return true;
return false;

Finally, I'd like to add that I would either create a new class deriving from QtreeNode that implemented a method like nodeDifference or just add it if you control the source of QtreeNode, which can clean up your code further, i.e.

bool signal(QtreeNode *&orig, QtreeNode *&n, int tolerance) {
  if (n->isLeaf())
     return (orig->nodeDifference(*n) > tolerance);
  else
     return (signal(orig, n->neChild, tolerance) ||
             signal(orig, n->nwChild, tolerance) ||
             signal(orig, n->swChild, tolerance) ||
             signal(orig, n->seChild, tolerance));
 }

Michael Anderson · Accepted Answer · 2011-03-30 04:47:11Z

1

You'll hit every leaf in your quadtree this way. Instead you want to break as soon as you've found it. To do that you need to change

signal1=signal(orig, n->neChild, tolerance); 
signal2=signal(orig, n->nwChild, tolerance);
signal3=signal(orig, n->swChild, tolerance);
signal4=signal(orig, n->seChild, tolerance);

if(signal1 || signal2 || signal3 || signal4)
    return true;
else return false;

to

return signal(orig, n->neChild, tolerance) || 
       signal(orig, n->nwChild, tolerance) ||
       signal(orig, n->swChild, tolerance) ||
       signal(orig, n->seChild, tolerance);

answered Mar 30, 2011 at 4:47

Michael Anderson

74.3k9 gold badges148 silver badges196 bronze badges

Collectives™ on Stack Overflow

Recursive boolean function

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related