这段代码是否符合递归的定义？

Question

这段代码是否符合递归的定义？

3

我有一段代码，我怀疑它是否符合递归的定义。我的理解是，代码必须调用自身，完全相同的函数。我也质疑编写这种代码是否会增加额外的开销，这可以通过使用递归来看到。你有什么想法？

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

- dekz

请在以后将您的代码剪裁为仅包含相关部分。 - danio

5个回答

5

是的，因为你有某些函数在调用自身。根据定义，这是直接递归。如果函数A()调用函数B()，函数B()反过来（直接或间接地）再次调用函数A()，那么你也可能会有间接递归。

- sharptooth

他在哪里有调用自身的函数？他有另一个对象调用了这个函数，但不是 this->callMyFuction()。 - Shaihi

1

我的C++不是很好，但即使调用完全相同的函数，它也作为不同对象的一部分被调用，所以在我看来它并没有真正地调用自己。 - IVlad

构造函数通过 new dhObject 调用自身。update 调用 update，traverse 也是如此。基本上，每当您使用相同对象定义某些内容（例如函数 update()），就会出现递归。 - jpalecek

6

每个成员函数都有一个隐式的this参数。因此，即使它被称为 functionImpl(someOtherInstance, parameter) 而不是 functionImpl(thisInstance, parameter)，它仍然调用自身，只是隐式参数不同。 - sharptooth

@dekz：为了确定是否进行了优化，您需要检查发出的汇编代码。使用小深度递归通常是可以的-开销将最小化，但代码不适用于更大的输入-一旦输入太大，它将导致堆栈溢出并崩溃。 - sharptooth

显示剩余4条评论

1

看起来在traverse()和update()方法中使用了递归，深度由对象集合的物理几何形状控制。

如果这是您实际的类，我建议您做以下几点：

在使用numChildren之前，请检查其上限，以防有人错误地传入一个非常巨大的数字。
如果将在多线程环境中使用此代码，您可能需要同步访问子对象。
考虑使用容器而不是分配数组。我没有看到析构函数，因此如果删除此对象，则会泄漏数组存储和子项的内存。

- Amardeep AC9MF

对象的一部分，包括析构函数，因其不相关而被剪掉了。 - dekz

1

如果你所担心的只是递归开销，那么重要的是要测量您的堆栈深度。无论您是否在递归工作，如果您的堆栈深度为100个调用，则无关紧要。

- Skilldrick

这是关于4个总对象，每个对象有1-2个子对象。因此，我认为不会存在过多的开销。你同意吗？ - dekz

是的。递归的唯一问题就是当你深入到非常深的层次时。 - Skilldrick

0

调用这些方法(traverse或update)之一将导致在每个子节点上调用相同的方法。因此，这些方法不是递归的。相反，它是一个递归算法：它在对象的逻辑树上递归应用。

调用堆栈的深度直接由算法操作的数据结构确定。

实际发生的是这样的(伪代码)：

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

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

   [do something with o]
}

- Andy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- anon · Accepted Answer

这是一个定义/吹毛求疵的问题。在这个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上调用该函数的对象与最初调用的对象不同。但我认为每个人都会同意这是一个递归函数。