此代碼是否遵循遞歸的定義？

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

這是一個定義/挑剔的問題。在這個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個電話，則無關緊要。