Turning recursive to iterative form

[rmxhaha]

So I have a code like this one below :

	void get_sum( INNER_ID id, vector<INNER_ID>& dont_check )
	{
		vector<INNER_ID> below = get_below( id );
		vector<INNER_ID>::iterator second;

		for( auto it = below.begin(); it != below.end(); ++ it ){
			second = find( dont_check.begin(), dont_check.end(), *it );

			if( second == dont_check.end() ){
				dont_check.push_back( *it );
				get_sum( *it, dont_check );
			}
		}
	}

int main(){
	vector<INNER_ID> return_;
	get_sum( 0, return_ );
	for( auto it = return_.begin(); it != return_.end(); ++ it ){
		printf("%i\n", *it );
	}

	return 0;
}

I use this algorithm for my "crappy" physic engine, so the point of this algorithm is to get the sum of mass below an object. get_below( id ) function can get the ids of what object is below them.

But before I need ids of the object below them to apply impulse, force, and some other physic stuff.

One object doesn't neccesarrly rest on top of one object, it can rest on 2 object or more.

when I look at it, it resemble a tree, maybe it's not. I just don't really know very much about tree algorithm

I cannot optimize a recursive code so I think, I better turn this into an iterative but I cannot seem to find a way to do that

can anyone help me ?

Thanks in advance for your reply....

[abhishekm71]

Is your present code working fine? Do you want to change it to iterative only to optimize it?

How large are you expecting your input data set to be?

Your code is not clear. It'll help if you show us your implementation for get_below( id ) function (and other functions if any) as well.

[rmxhaha]

This current code work just fine and there won't be much of a problem because now I only have smt like 100 objects in the scene.

There will probably be around 2000 objects later on,

        map< ID, Body > bodies; 

	vector<INNER_ID> get_below( ID id ){
		auto it = bodies.find( id );

		if( it == bodies.end() ) // return empty vector
			return vector<INNER_ID>(); 
		
		return it->second.getCollidedIDsBelow();
	}

and somewhere within Body class

class Body {
public:
// some other thing....

			const vector<INNER_ID>& getCollidedIDsBelow() const {
				return m_below;
			}
private:
// some other thing....

			vector<INNER_ID> m_below;
}

I probably cannot show you "Body" class because it is 300 line long right now with many debug code which kinda hard to read

get_below is a function to get the list of objects that the current object is resting on.

I get confused from time to time in recursive codes
Some problem like, where can I put the early out
and does this code take more time allocating memory than doing the logic
and is there better ways to write this

[Smac89]

void get_sum( INNER_ID id, vector<INNER_ID>& dont_check ) {
	vector<INNER_ID> below, mule;
	vector<INNER_ID>::iterator second;
	mule.push_back(id);
	
	for ( auto pak = mule.begin(); pak != mule.end(); ++pak ) {
		below = get_below( *pak );
		for( auto it = below.begin(); it != below.end(); ++it ) {
			second = find( dont_check.begin(), dont_check.end(), *it );
			if( second == dont_check.end() ){
				dont_check.push_back( *it );
				mule.push_back( *it );
			}
		}
	}
}

EDIT:
Just realised that you might want child objects to immediately follow the parent. In which case, recursion is the only way to achieve this (I think)

[rmxhaha]

I start thinking again and again, I find one iterative solution, I try and it failed I don't know why,, well I need to experiment with things some more times

recursive is not so much a bother but I think
passing the same reference over and over again seems odd