Simpler recursive solution?

[quirkyusername]

I have this horrible piece of code

void TNode::CreateMoveTree()
{
	CreateNextRowOfMoves();
	int numChildren = GetNumChildren();

	for (int i=0; i<numChildren; i++)
	{
		GetChild(i)->CreateNextRowOfMoves();

		int numChildren2 = GetChild(i)->GetNumChildren();

		for (int j=0; j<numChildren2; j++)
		{
			GetChild(i)->GetChild(j)->CreateNextRowOfMoves();

			int numChildren3 = GetChild(i)->GetChild(j)->GetNumChildren();

			for (int k=0; k<numChildren3; k++)
			{
				GetChild(i)->GetChild(j)->GetChild(k)->CreateNextRowOfMoves();
			}
		}
	}
}

which, using my tree class, creates a tree of valid moves 4 branches deep. I know there must be a iterative recursive solution that does this better, and then I'd be able to pass in a parameter for how many branches deep I want to go too. Making this go a couple of branches deeper the way it is now would be horrible both to write and to read.

Has anyone got tips on how they usually approach coming up with iterative solutions? I just can't seem to see how to approach this.

Thanks x

[coder777]

the answer is recursion:

void TNode::CreateMoveTree()
{
	CreateNextRowOfMoves();
	int numChildren = GetNumChildren();

	for (int i=0; i<numChildren; i++)
	{
		GetChild(i)->CreateMoveTree(); // note: call CreateMoveTree()
        }
}

[quirkyusername]

That's what I meant, damn, got the words mixed up. Thanks for the reply coder777, wouldn't that cause an endless loop though? The probelm I have really is that I'm not sure how to do it recursively because I don't know how to store how many branches have been done so far.

[quirkyusername]

It does indeed go into an infinite loop, and cause a stack overflow

[m4ster r0shi]

#include <iostream>
using namespace std;

void f(int rec_level=0)
{
    if (rec_level==4) return;

    cout << "rec_level: " << rec_level << endl;

    f(rec_level+1);
    f(rec_level+1);
}

int main()
{
    f();

    cin.get();
    return 0;
}

[coder777]

wouldn't that cause an endless loop though?

no. it will end when there're no more children. Btw better check if GetChild() does return null.


EDIT: it will crash if you produce endless children ;)

[quirkyusername]

no. it will end when there're no more children.

CreateNextRowOfMoves() creates children, the code doesnt fill an already existing tree, it takes one node and adds four more rows of moves. If CreateMoveTree() calls CreateNextRowOfMoves() then it will keep making children until it crashes.

[firedraco]

The problem was to get a tree 4 levels deep...Tbh, I'd say that the iterative solution is better since you don't need to pass extra variables or recurse.

[coder777]

well m4ster r0shi showed how to solve it (if the level is indeed the indicator):

void TNode::CreateMoveTree(int level)
{
	if(level < 4)
	{
	    CreateNextRowOfMoves();
	    int numChildren = GetNumChildren();

	    for (int i=0; i<numChildren; i++)
	    {
		    GetChild(i)->CreateMoveTree(level + 1); // note: call CreateMoveTree()
            }
        }
}

And yes, the end it the weak spot of a recursion

_{I thought that CreateNextRowOfMoves(); would know when not to create children}