How to avoid stack overflow in deep tree recursion

Question

I've read many similar articles, I apologise if this has already been answered, but I'm still stuck.

I'm coding a function to populate a tree, each node having four branches, which will store the possible manipulation of states of the "eight tile puzzle" i.e. http://www.8puzzle.com/images/8_puzzle_start_state_a.png

The problem is I've reached, what I believe to be, stack overflow, due to the heavily recursive nature of the problem at hand.

Tail recursion seems like the solution, though I'm not sure if it is relevant/possible or how to implement it in this instance. Code follows:

void Tree::insert(string &initialState, const string &goalState, tree_node *&inNode){
cout<<"insert called"<<endl;
depth++;
cout<<depth<<endl;
string modState;
int zeroPos=0;

if(initialState==goalState){
    cout<<"*    *   *   GOAL    *   *   *"<<endl;
    getchar();
    exit(0);
}   

if(inNode==NULL){//is this the first node?

    inNode = new tree_node(initialState);       
    root=inNode;
    inNode->parent=NULL;
    insert(initialState, goalState, inNode);
}else{
    inNode->state = initialState;

    for(zeroPos=0;zeroPos<initialState.size();zeroPos++){//where is the empty tile?
        if(initialState[zeroPos]=='0'){
            break;
        }
    }
    //left
    if(zeroPos!=0 && zeroPos!=3 && zeroPos!=6){//can the empty tile move left?

        modState=initialState;
        modState[zeroPos]=modState[zeroPos-1];
        modState[zeroPos-1]='0';

        if(isOriginal(modState, inNode) ){//does this state already exist?

            cout <<"left  " << modState[0]<<modState[1]<<modState[2]<<endl;
            cout <<"left  " << modState[3]<<modState[4]<<modState[5]<<endl;
            cout <<"left  " << modState[6]<<modState[7]<<modState[8]<<endl;

            inNode->l = new tree_node(modState);    
            inNode->l->parent= inNode;
            if(inNode->l != NULL){
                insert(modState, goalState, inNode->l);
            }
        }
    }

    }
 }
}

I haven't gone through your code, but I'd be surprised if you are getting a stack overflow on the 8-puzzle if your algorithm is working properly. — Flash
– Flash, Commented Apr 30, 2011 at 5:43
Perhaps a tree of all states isn't the best possible implementation? — BlueTalon
– BlueTalon, Commented Apr 30, 2011 at 5:48
I probably should have mentioned I intended to run various search algorithms, to find steps to the goal state, and record their efficiency in various aspects (time, memory usage etc.). — BlueTalon
– BlueTalon, Commented Apr 30, 2011 at 5:54
@RemnantXO Why are you creating a tree of states before running the search algorithms? — Flash
– Flash, Commented Apr 30, 2011 at 6:09
Hmm. Is there an alternate way to run them? I can't think how to search the states without having them arranged in some structure. Perhaps I'm just being remarkably dimwitted and missing the obvious? — BlueTalon
– BlueTalon, Commented Apr 30, 2011 at 6:34

Joseph Lisee · Accepted Answer · 2011-04-30 07:32:37Z

3

This is a very generic answer, but have you tried to explicitly manage your stack through something like a heap allocated queue or a stack? Basically don't use actually function calls, just push and pull things off your own stack/queue. They cover non-recursive graph traversal algorithms here (both depth first, and breadth first search).

answered Apr 30, 2011 at 7:32

Joseph Lisee

3,52128 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

atoMerz · Accepted Answer · 2011-04-30 07:15:06Z

0

Optimize your code, meaning only keep those nodes you need. For example only keep leaf nodes (I mean the ones you haven't yet expaneded). And yes you can search the tree while building it, write a function to measure the distance between your current state and your goal state, its called heuristic. There's also a better algorithm that solves 8puzzle, it's called A*, I suggest you google it.

answered Apr 30, 2011 at 7:15

atoMerz

7,73216 gold badges65 silver badges104 bronze badges

2 Comments

BlueTalon Over a year ago

Aren't the nodes, being dynamically allocated, stored on the heap though? I will be implementing A* but I'm comparing a range of search functions.

atoMerz Over a year ago

yes, but you could delete the nodes that you have already expanded that is when you added all it's children, remove the node itself.

Collectives™ on Stack Overflow

How to avoid stack overflow in deep tree recursion

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related