Learn VisualBasic.NET with Me: recursion

It’s going to be a lesson about recursion. It’s strictly beginner level.

I don’t have any code today, because I was working the polls yesterday, and spent most of today’s worktime tuning that file copier. I hit a big problem because of some confusing, mis-coded loops. Here’s the scenario in pseudocode (I don’t want to fire up the Windows box just to get this code).

for each item in collectionA
    if type of item is Layer then
        processLayer item
    else if type of item is LayerGroup then
        for each subItem in item
            if type of subItem is Layer then
                processLayer subItem
            else if type of subItem is Raster
                processRaster subItem
            end if
        end for
    end if
end for

If you can really read this, it does a 1-level deep exploration when the item is a LayerGroup.

It’s implid that an item can be a Layer, a LayerGroup, or a Raster.

Well, the problem was that sometimes, Rasters were at the top level. Oooops. The fix is to use a recursive function. A recursive function is a function that calls itself.

That definition usually doesn’t explain, too well, to most people, what a recursive function is. A recursive function, in this situation, is used to process a hierarchy of objects. In the same way that a loop is useful to process a list of objects, a recursive function is useful to process a hierarchy of objects. Whenever we have an object that contains other objects, the recursive function is used on that object.

Here’s the new code:

define function F( collectionA )
    for each item in collectionA
        if type of item is Layer then
            processLayer item
        else if type of item is Raster then
            processRaster item
        else if type of item is LayerGroup then
            F( item )
        end if
    end for
end for

This way of doing it is not just more compact, it’s also lacking the bug. It will also process not only two-layer hierarchies: it’ll handle all hierarchies.

Now, if you already write recursive functions, you may not believe this, but the original algorithm above was being used. It’s just more evidence that it’s still pretty hard to grasp recursion. It doesn’t really make sense until you use it to do something like seek files in a directory hierarchy. Even then, it might not make sense to everyone.

These days, recursion is not so common anymore, because a lot of apps use database tables rather than hierarchies of files.

Denouement

There’s a slightly unhappy “undoing” to this lesson. The problem is that the type of the initial collection differs from the type of the collection within the hierarchy. I operated under the assumption that I could use the Object object to hold the collection. In fact, I had to coerce the object to one of two types to do what I wished.

My error requires (as far as I know) that I, basically, duplicate code, with one for each type of collection. Perhaps there’s a solution available using generic programming, and that I just don’t know it yet.

Here’s the code:

    Public Function ProcessLayerSourceCollection(ByVal lsc As Object) As Collection
        Dim cOutput As Collection = New Collection()
        Dim pFeatureLayer As IFeatureLayer
        Dim pRasterLayer As IRasterLayer
        Dim pCompositeLayer As ICompositeLayer
        Dim s As String
        Dim i As Integer

        If TypeOf lsc Is ICompositeLayer Then
            Dim c As ICompositeLayer = lsc
            For i = 0 To c.Count - 1
                If TypeOf c.Layer(i) Is IFeatureLayer Then
                    pFeatureLayer = c.Layer(i)
                    For Each s In LayerSources(pFeatureLayer)
                        cOutput.Add(s)
                    Next
                ElseIf TypeOf c.Layer(i) Is IRasterLayer Then
                    pRasterLayer = c.Layer(i)
                    For Each s In RasterSources(pRasterLayer)
                        cOutput.Add(s)
                    Next
                    For Each s In InfoDirContents(pRasterLayer.FilePath())
                        cOutput.Add(s)
                    Next
                ElseIf TypeOf c.Layer(i) Is ICompositeLayer Then
                    pCompositeLayer = c.Layer(i)
                    For Each s In ProcessLayerSourceCollection(pCompositeLayer)
                        cOutput.Add(s)
                    Next
                End If
            Next
        ElseIf TypeOf lsc Is IMap Then
            Dim c As IMap = lsc
            For i = 0 To c.LayerCount - 1
                If TypeOf c.Layer(i) Is IFeatureLayer Then
                    pFeatureLayer = c.Layer(i)
                    For Each s In LayerSources(pFeatureLayer)
                        cOutput.Add(s)
                    Next
                ElseIf TypeOf c.Layer(i) Is IRasterLayer Then
                    pRasterLayer = c.Layer(i)
                    For Each s In RasterSources(pRasterLayer)
                        cOutput.Add(s)
                    Next
                    For Each s In InfoDirContents(pRasterLayer.FilePath())
                        cOutput.Add(s)
                    Next
                ElseIf TypeOf c.Layer(i) Is ICompositeLayer Then
                    pCompositeLayer = c.Layer(i)
                    For Each s In ProcessLayerSourceCollection(pCompositeLayer)
                        cOutput.Add(s)
                    Next
                End If
            Next
        Else
            Debug.WriteLine("Unknown type of lsc.")
        End If
        Return cOutput
    End Function

It’s still slightly better than the original, because it displays the explicit parallels between the two parts. That will make it a little easier to maintain. A slightly better factoring would have been to make separate functions to process each type.