how to use loop instead of recursion

Question

1.80/5 (2 votes)

See more:

As follow:

C++

void divconqrecurse(struct mesh *m, struct behavior *b, vertex *sortarray,
                    int vertices, int axis,
                    struct otri *farleft, struct otri *farright)
{
  struct otri innerleft, innerright;
  int divider;
  if (vertices == 2) 
  {
    //end statement
    //that assign to farleft and farright
    return;
  }
  else if (vertices == 3) 
  {
    //end statement
    //that assign to farleft and farright
    return;
  } 
  else 
  {
    divider = vertices >> 1;
    divconqrecurse(m, b, sortarray, divider, 1 - axis, farleft, &innerleft);
    divconqrecurse(m, b, &sortarray[divider], vertices - divider, 1 - axis,
                   &innerright, farright);
    mergehulls(m, b, farleft, &innerleft, &innerright, farright, axis);
  }
}

Posted 8-Dec-14 20:48pm

gig886

Updated 9-Dec-14 21:18pm

v3

Add a Solution

Comments

Kornfeld Eliyahu Peter 9-Dec-14 3:32am

Use some stack variable to push in values for next iterations...
(I have a sample in C# if you are interested)

gig886 10-Dec-14 3:06am

thank you for your code

nv3 9-Dec-14 8:06am

Why would you want to replace the recursion by a loop? In your example this will probably not bring much speed improvement. What you gain by reducing the function call overhead you will lose by the dynamic allocation of your otri structures.

If you still want to put it as a loop, then please also show the code for mergehulls and fill in the cases of vertices==2 and vertices==3. (I wonder what happens if you call your function with vertices==1).

gig886 10-Dec-14 3:15am

the number of divconqrecurse call too many ,some error

Maciej Los 10-Dec-14 2:46am

I'm almost sure, i saw this question before...

gig886 10-Dec-14 3:31am

yet, it is trangle.cpp

2 solutions

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Eugen Podsypalnikov · Answer 1 · 2014-12-09T05:02:00

A potential starting :) :

C++

#include <stack>
#include <memory>

class ParList
{
  struct mesh *m;
  struct behavior *b;
  vertex *sortarray;
  int vertices;
  int axis;
  struct otri *farleft;
  struct otri *farright;

public:
  ParList()
  {
    ..
  }
  ParList(../*all needed pars*/)
  {
    ..
  }
  ParList(const ParList& src)
  {
    ..
  }
  const ParList& operator=(const ParList& src) {..}

  int getVertices() const { return vertices; }

  //..
};

extern void mergehulls(const ParList& listPars);


void TheLoop(const ParList& listPars)
{
  std::stack<std::unique_ptr<ParList>> stackParLists;
  stackParLists.push(std::make_unique<ParList>(listPars));

  while (stackParLists.size())
  {
    bool bCurListValid(false);

    ParList curList;
    ParList* pcurList(stackParLists.top().get());
    if (pcurList)
    {
      curList = *pcurList;
      bCurListValid = true;
    }
    stackParLists.pop();

    enum { retVert2 = 2, retVert3 };

    if (bCurListValid &&
        retVert2 != curList.getVertices() &&
        retVert3 != curList.getVertices()) {
      
      ParList leftList(curList);
      // discover pars of leftList:
      //..here :)

      // push the leftList:
      stackParLists.push(std::make_unique<ParList>(leftList));

      ParList rightList(curList);
      // discover pars of rightList:
      //.. here :)

      // push the rightList:
      stackParLists.push(std::make_unique<ParList>(leftList));

      // make the merged list
      ParList mergedList(curList);
      //.. here :)

      // call for the merged list
      mergehulls(mergedList);

      // now the left- and right-lists will be precessed
    }
  }
}

Kornfeld Eliyahu Peter · Answer 2 · 2014-12-09T21:21:00

Per OP request...

This code search in an ASP.NET control tree for one with the specific ID.
Such control tree is built for the classic recursive search as every node looks exactly the same, but here I show a not-recursive approach.
I also used the very same idea in a pixel-level search inside an image where I also measured performance - the non-recursive performed a hundred times better...

C#

public static Control FindControlById ( Control oParent, string szID )
{
	Control oControl = null;
	Stack oStack = new Stack( );

	oStack.Push( oParent );

	while ( oStack.Count != 0 )
	{
		Control oCheckControl = ( Control )oStack.Pop( );

		if ( oCheckControl.ID == szID )
		{
			oControl = oCheckControl;

			break;
		}
		else if ( oCheckControl.HasControls( ) )
		{
			foreach ( Control oChildControl in oCheckControl.Controls )
			{
				oStack.Push( oChildControl );
			}
		}
	}

	return ( oControl );
}

how to use loop instead of recursion

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

how to use loop instead of recursion

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Existing Members

...or Join us