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

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

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

Answer 2

Это вопрос определения/nitpicking. В этой функции 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 3

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

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

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

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

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

    [do something with o] 
} 

Answer 4

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

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

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

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

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

Answer 5

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