I have heard a lot about how recursion is bad, and why we should use collections instead and that collections are faster/safer, I believe it, but recursion has it's moments when it proves to be more useful than collections.
When you have that typical scenario of nodes, with one child and one parent (or many of both, etc) and then you call a function that calls the same function of either the parent of the child, that's a recursive function call, it will iterate all the elements that satisfy the criteria, such as "Draw all the children of this node", then we call draw on the parent, and the parent call draw on the children, etc.
What I think is bad about recursion is when the function being used recursively needs to pass arguments to be further tested down the line of nodes, or when the function itself returns a value to be processed by the parent, this is bad simply because we need to allocate memory for as long the functions we are using are alive (memory in the stack), for example if a parent node needs to count all it's children it could send an int by reference down the line and tell the children to add one or the children could return an int that's equal to the current number + 1, the stack wont release memory until the functions are finalized.
This could be avoid nevertheless, if you must have something to be analyzed down the line then you could make use of a "static" variable, that means you just need to set that variable once and all the nodes will know about it (a local static variable), that means you are not really allocating memory per call, just looking at memory already available to you.
I used recursion to add new elements to my drawing sorting, this proved to be quite fast and efficient, so instead of using a collection I used a node system that holds an "IDrawSorted" type of object and calls draw on it whenever the parent node needs to draw, code example:
public class SortingNode
{
public static SortingNode TopParent;
static Poolean NodePool = new Poolean(1000, 100);
public static SortingNode FindingAPlace;
public SortingNode Child;
public SortingNode Parent;
public IDrawSorted Drawer;
public int Z;
In the fields we have 2 static variables, one for the node that is being analyzed and another one for the current top parent, this node class is also pooled, take a look at my previous post to know about how the Poolean class works. After that you can see that the node can contain a child and a parent, as well as the information of the IDraw (The actual drawing object and it's Z position for Z sorting).
public static void Create(out SortingNode Vessel)
{
NodePool.Get(out Vessel);
}
As a rule I never ever use "new" in my code design, simply because using new on objects can cause memory leaks, so all my objects are properly managed, using factory pattern methods to get "instantiated" since they really are not being created on the fly, they already live in a pool.
public void Add()
{
if (FindingAPlace.Z <= Z)
{
if (Child != null)
{
Child.Add();
}
else
{
Child = FindingAPlace;
FindingAPlace.Parent = this;
}
}
else
{
if (Parent == null)
{
//if a node has no parent, it is the head.
TopParent = FindingAPlace;
FindingAPlace.Child = this;
Parent = FindingAPlace;
}
else
{
Parent.Child = FindingAPlace;
FindingAPlace.Child = this;
FindingAPlace.Parent = Parent;
Parent = FindingAPlace;
}
}
FindingAPlace = null;
}
So, this is a recursion function, as you can see it does not take any arguments and it returns nothing, so prior to call this function the information you want to analyze has to be pre loaded to the static variable inside the class, this is accomplished by accessing them by "SortingNode.FindingAPlace = YourDrawer;", this way we only set it once, and then send it to analyze.
In this function we are looking if the current Z value we are passing through the static IDrawSorted is smaller or equal to the current's IDrawSorted living in the node, we will check if it has a child in the event that it is smaller or equal, so we further test down the line until we find a place were to place this new node, this is faster than a normal collection simply because I do not need to change or push down all the resting elements down the line by one because if we need to insert something in between the line we simply just change the references pointing to the parents and children to of the new node.
public void Draw()
{
if (Child != null)
{
Child.Draw();
}
Drawer.Draw();
}
Recursively calling draw on every children, this is a secondary function.
public void StartDrawing()
{
if (Parent != null)
{
Parent.StartDrawing();
}
else
{
Draw();
}
}
this is the the entry point to the drawing class, I do it this way in case that the node that called "StartDrawing" might not be the current top node, therefore we need to find the top node to start calling draw.
public void Recycle()
{
if (Child != null)
{
Child.Parent = null;
Child.Recycle();
}
Child = null;
NodePool.ReturnPoolable(this);
}
}
Finally we have a recycle method to put the entire collection back into the pool when we don't need it anymore.
And that concludes my recursion method and how I use them to sort my drawing, this is working nicely in the Xbox. Currently I am working on an Xbox title because I am waiting for the new Windows phone 8 to come out as well as the new Visual Studio, once that's out I will be porting all my code to C++.
