Этот код соответствует определению рекурсии?

Question

У меня есть фрагмент кода, в котором я сомневаюсь, как реализация рекурсии по определению.Насколько я понимаю, код должен вызывать саму себя, точно такую ​​же функцию.Я также подвергаю сомнению, добавляет ли написание кода таким образом дополнительные издержки, которые можно увидеть при использовании рекурсии.Что ты думаешь?

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

Это вопрос определения / придирки. В этой функции C:

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

Является ли функция рекурсивной? Я бы сказал, да, хотя он вызывается на разных объектах. Поэтому я бы сказал, что ваш код также рекурсивный. Чтобы взять еще более экстремальный пример:

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

То, что функция вызывается в XXX, явно не то, что было вызвано изначально. Но я думаю, что все согласятся, что это рекурсивная функция.

Answer 2

Да, поскольку у вас есть определенные функции, вызывающие себя. По определению это прямая рекурсия . Вы также можете иметь косвенную рекурсию , если бы у вас была функция A(), вызывающая функцию B(), функция B() по очереди (прямо или косвенно) снова вызывала функцию A().

Answer 3

Если все, что вас беспокоит, - это издержки рекурсии, тогда важно измерить, насколько глубоко уходит ваш стек. Не имеет значения, работаете ли вы рекурсивно или нет, если ваш стек имеет глубину 100 вызовов.

Answer 4

Похоже на рекурсию в методах traverse () и update () с глубиной, контролируемой физической геометрией вашей коллекции объектов.

Если это ваш реальный класс, я бы порекомендовал несколько вещей:

1. Проверьте верхнюю границу numChildren, прежде чем использовать ее, чтобы кто-то не ошибся в огромном количестве.Возможно, вы захотите синхронизировать доступ к дочерним объектам.

2. Рассмотрите возможность использования контейнеров вместо выделения массива.Я также не вижу деструктора, поэтому вы потеряете память для хранения массива и потомков, если этот объект будет удален.

Answer 5

Вызов одного из этих методов (обход или обновление) приведет к вызову того же метода для каждого потомка. Таким образом, методы не являются рекурсивными. Это рекурсивный алгоритм: он применяется рекурсивно к логическому дереву объектов.

Глубина стека вызовов напрямую определяется структурой данных, с которыми работает алгоритм.

Что действительно происходит, так это (псевдокод):

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

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

   [do something with o]
}