It's deja-vu all over again - recursion
One of the subjects that made me nervous when taking computer science classes in college was recursive programming. It was easy to accidentally write a recursive (i.e. never-ending} program but it was sometimes hard for me to determine when I should write one on purpose. Like any other tool, it is important to know which situations call for recursive programming and which don't. It seemed that as the assignments became more complicated, the more I had to rely on recursive programming.
A sure-fire way to accidentally end up with an endless loop is to forget to provide some way to terminate a process. A never-ending program eventually runs out of memory to store intermediate results which ends up with an "Out of stack space" error message. Fortunately, this error message in and of itself is a clear sign that you've created an endless loop because it's relatively hard to run out of stack space. Typically, stack space is used to store the arguments of a function when it is called as well as the state of the calling procedure. To run out of stack space, you'd need to have to call a large number of procedures, each within the other. This is kind of what recursion does, except that you can do the same thing with only one procedure if you don't have a way to exit the loop.
So when is recursion appropriate? Knowing isn't always obvious.If you have a procedure that is carrying out task A and needs to stop and carryout identical task B, then recursion might help. A classic example, is scanning files in folders and sub-folders. The procedure first iterates through the first folder and when it encounters another folder, has to repeat itself. Another example is sorting arrays. You compare two items and then swap one with the other And then you repeat this recursively. Another flag that recursion may help is if you find yourself nesting several loops within themselves.
One VB.NET program that I currently maintain iterates through the nodes in an XML schema (XSD) and creates a help topic for elements and complex types. The program uses recursion to look for parent elements for elements inside complex types. So the algorithm goes something like this: read through the nodes until you encounter complexType node A. Then continue reading through the nodes inside the type until you find element X. Now read each parent node of element X until you find an element with type A. This element is a parent of element X. If the element is not of type A, continue to read until you find another element and compare its type with type A. Without recursion. imagine how many Do..Until loops and If Then Else loops you would need to move though the element nodes comparing the element's types and then moving to the next element node and so on. With recursion, the amount of code to do this is relatively small. A simplified version is shown here:
Private Function GetNamedParent(ByVal itemNode As XmlNode, itemType) As XmlNode
Dim tempParent As XmlNode
Dim tempTypeNode As XmlNode
Try
tempParent = itemNode.ParentNode
tempTypeNode = tempParent.Attributes("type").Value
' Move up the chain until you get to a node with
' a name attribute, such as an element or type.
If tempTypeNode = itemNode.Attributes("type").Value Then
Return tempParent
Else
Return GetNamedParent(tempParent)
End If
Catch excpt As System.Exception
' MessageBox.Show("Error in GetNamedParent function: " & excpt.Message)
End Try
End Function 'GetNamedParent
The function receives the element in the complex type as an argument. The element's parent node is found and assigned to a temporary node variable. Then the parent node's type is compared to the type of the input element. If they match, the temporary element node must be a parent of the input element and its value is returned to the calling procedure. Otherwise the function is called again until a parent is found. Hopefully this explanation has given you a better understanding of recursion and when to use it in your own programs.