Discount Stack Overflows


If you’re sick of paying through the nose at your local Wal-Mart or Best Buy on ways to overflow your stack, you could be saving hundreds by just doing it yourself! While working on a recent project I accidentally made a very rookie mistake when creating a recursively called Depth First Search function that resulted in overflowing the stack from too many function calls.

What I did was essentially this:

bool recursiveFunction(Graph* g, node* next)

{

//base case 1

return false;

//base case 2

return true;

//recursive case

return (recursiveFunction(g,next->neighbor1) ||         recursiveFunction(g,next->neighbor2);

}

What I wasn’t doing was checking a neighbor node to see if I had searched it first before moving onto the other cases. So basically the call stack looked like this:

recursiveFunction(g, Node1);
recursiveFunction(g, Node2);
recursiveFunction(g, Node1);
recursiveFunction(g, Node2);

recursiveFunction(g,Node1);

and on and on as two neighboring Nodes continually check each other without any indication that they should be. My mistake isn’t restricted to just DFS on a graph, but really any sort of graph search. A tree is not so big of a deal because nodes typically do not search their parents and thus the search is always “down” the tree, so our problem is really restricted to graphs.

So the challenge becomes designing your system to easily check to see whether a node in your graph has been searched before, and there are a million ways to do it, from adding a reference to the node in a container of searched nodes to building a ‘searched’ boolean into your node structure that can be flipped, although this will require more time.

This is a lighthearted, easy fix for most programmers, but just goes to show once again that the Design stage of software creation is just as important as the Implement one; although we can all agree the Implement stage is infinitely more fun to do 🙂

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: