CODEWITHSUNDEEP
c++recursion
dekz
dekz

Reputation: 815

Does this code follow the definition of recursion?

I have a piece of code which I am doubting it as a implementation of recursion by its definition. My understanding is that the code must call itself, the exact same function. I also question whether writing the code this way adds additional overhead which can be seen with the use of recursion. What are your thoughts?

class dhObject
{
public:
   dhObject** children;
   int numChildren;
   GLdouble linkLength; //ai 
   GLdouble theta; //angle of rot about the z axis
   GLdouble twist; //about the x axis
   GLdouble displacement; // displacement from the end point of prev along z
   GLdouble thetaMax;
   GLdouble thetaMin;
   GLdouble thetaInc;
   GLdouble direction;

   dhObject(ifstream &fin)
   {
      fin >> numChildren >> linkLength >> theta >> twist >> displacement >> thetaMax >> thetaMin;
      //std::cout << numChildren << std::endl;
      direction = 1;
      thetaInc = 1.0;
      if (numChildren > 0)
      {
         children = new dhObject*[numChildren];
         for(int i = 0; i < numChildren; ++i)
         {
            children[i] = new dhObject(fin);
         }
      }
   }

   void traverse(void)
   {
      glPushMatrix();
      //draw move initial and draw
      transform();
      draw();
      //draw children
      for(int i = 0; i < numChildren; ++i)
      {
         children[i]->traverse();
      }
      glPopMatrix();
   }

   void update(void)
   {
      //Update the animation, if it has finished all animation go backwards
      if (theta <= thetaMin)
      {
         thetaInc = 1.0;
      } else if (theta >= thetaMax)
      {
         thetaInc = -1.0;
      }
      theta += thetaInc;
      //std::cout << thetaMin << " " << theta << " " << thetaMax << std::endl;
      for(int i = 0; i < numChildren; ++i)
      {
         children[i]->update();
      }
   }

   void draw(void)
   {
      glPushMatrix();
      glColor3f (0.0f,0.0f,1.0f);
      glutSolidCube(0.1);
      glPopMatrix();
   }

   void transform(void)
   {
      //Move in the correct way, R, T, T, R
      glRotatef(theta, 0, 0, 1.0);
      glTranslatef(0,0,displacement);
      glTranslatef(linkLength, 0,0);
      glRotatef(twist, 1.0,0.0,0.0);
   }
};

Upvotes: 3

Views: 263

Answers (5)

Andy
Andy

Reputation: 3743

Calling one of these methods(traverse or update) will have the effect of calling that same method an every child. So, the methods are not recursive. Instead, it's a recursive algorithm: it is applied recursively on the logical tree of objects.

The depth of the call stack is directly determined by the structure of the data on which the algorithm operates.

What really happens is this(pseudo code):

Function Traverse(object o)
{
   [do something with o]

   Foreach(object child in o.Children)
       Traverse(child);

   [do something with o]
}

Upvotes: 0

Skilldrick
Skilldrick

Reputation: 70889

If all you're worried about is the overhead of recursion then the important thing is to measure how deep your stack goes. It doesn't matter whether you're working recursively or not, if your stack is 100 calls deep.

Upvotes: 1

Amardeep AC9MF
Amardeep AC9MF

Reputation: 19064

Looks like recursion in the traverse() and update() methods with depth controlled by the physical geometry of your object collection.

If this is your actual class I would recommend a few things:

  1. Check the upper bound of numChildren before using it lest someone passes in a remarkably huge number by mistake.

  2. If this will be used in a threaded environment you might want to synchronize access to the child objects.

  3. Consider using containers instead of allocating an array. I don't see a destructor either so you'd leak the memory for the array storage and the children if this object gets deleted.

Upvotes: 1

anon
anon

Reputation:

This is a matter of definition/nitpicking. In this C function:

void traverse( tree * t ) {
    if ( t != 0 ) {
        traverse( t->right );
        traverse( t->left );
    }
}

Is the function recursive? I would say yes, even though it is being called on different objects. So I would say your code is also recursive. To take an even more extreme example:

unsigned int f( unsigned int n ) {
    if ( n = 0 ) {
       return 0; 
    }
    else {
       return f( n - 1 );   // XXX
    }
}

The thing the function is being called on at XXX is obviously not the same thing it was originally called on. But I think everyone would agree this is a recursive function.

Upvotes: 6

sharptooth
sharptooth

Reputation: 170559

Yes, since you have certain functions calling themselves. By definition that is direct recursion. You could also have indirect recursion if you had function A() calling function B(), function B() in turn (directly or indirectly) calling function A() again.

Upvotes: 5

Related Questions