Does this code follow the definition of recursion?

Question

Hi All,

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

Answer 1

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.

Answer 2

Recursion only occurs when your function calls itself. In your case, they aren't the same functions. traverse() calls traverse() for its children, and not itself.

In your example,

parent->traverse()

does not call itself. Instead, it calls

parent->children[i]->traverse()

so parent->traverse() really gets executed just once. This is the same with your update() method.

Answer 3

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.

Answer 4

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

Answer 5

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.

Answer 6

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.