Returning data from a recursive method
Sometimes you need to write a method that requires recursion to be elegant. Often that method needs to accumulate data between recursion levels
There are many ways to do so, and some are more elegant than others.
I like the Optional Parameter method: it requires no additional class or static (shared in VB) members and the client code doesn’t have to know anything about the method’s internals.
Try running the code below. It uses reflection to enumerate all the types in MSCorlib. It then uses various methods to get a list of the type and the types ancestral lineage (yeah I know that’s redundantJ)
For example, System.MulticastDelegate inherits from System.Delegate, which inherits from System.Object, so our list would have 3 entries.
This example doesn’t require recursion, but some algorithms are much better written recursively (see Area fill algorithm: crayons and coloring book for an example of recursion that uses a lot of stack, but is elegant)
Which one uses the most/least memory? Which one requires more client knowledge and/or prerequisite initialization? Which is easier to maintain over the years?
Start VS: File->New->Project->VB->WPF Application.
Replace the code in MainWindow.xaml.vb with the code below.
Hit F5
<Sample>
Imports System.Reflection
Class MainWindow
Private Sub MainWindow_Loaded(ByVal sender As Object, ByVal e As RoutedEventArgs) Handles Me.Loaded
Me.WindowState = Windows.WindowState.Maximized
Dim asm = Assembly.GetAssembly(GetType(Integer)) ' get assembly containing Integer (MSCorLib)
Me.Title = asm.FullName
Try
Dim TabCtrl As New TabControl
Me.Content = TabCtrl
'run the code, hit Ctrl-Tab to cycle through the resulting tabs
Dim lambdas(,) = {{"ByClass",
Function(typ As Type) As List(Of Type)
' this way requires a class instantiation and
' is more verbose
Dim result = GetListClassAncestryByClass(typ)
Return result
End Function},
{"Shared",
Function(typ As Type) As List(Of Type)
' this requires client to preinit a shared (yukky)
_ListType = Nothing ' must be init'd to 0 . Try commenting this out!
Dim result = GetListClassAncestryByShared(typ)
Return result
End Function},
{"ExtraParam",
Function(typ As Type) As List(Of Type)
'This way requires initializing a parameter
'into which to store the answer
Dim lst = New List(Of Type)
Dim result = GetListClassAncestryByExtraParam(typ, lst)
Return result
End Function},
{"ByOptParam",
Function(typ As Type) As List(Of Type)
' this way is nice and clean
' Couldn't do this in C# without Optional Parameters
Dim result = GetListClassAncestryOptParam(typ)
Return result
End Function},
{"ByLoop",
Function(typ As Type) As List(Of Type)
' this way works without recursion,
' so not really a good example of recursion :)
Dim result = GetListClassAncestryByLoop(typ)
Return result
End Function}
}
For i = 0 To lambdas.Length - 1 Step 2
Dim lstview As New ListView
For Each typ In asm.GetExportedTypes
Dim lstMems = lambdas(i \ 2, 1).invoke(typ)
Dim lev = ""
For Each itm In lstMems
lstview.Items.Add(String.Format("{0} {1} {2}", i \ 2, lev, itm))
lev += " "
Next
Next
TabCtrl.Items.Add(New TabItem With {.Header = lambdas(i \ 2, 0), .Content = lstview})
Next
Catch ex As Exception
Me.Content = ex.ToString
End Try
End Sub
Private Function GetListClassAncestryByClass(ByVal typ As Type) As List(Of Type)
Dim c = New CalcAncestry(typ)
Return c._ListType
End Function
Private Class CalcAncestry
Public Property _ListType As New List(Of Type)
Sub New(ByVal typ As Type)
RecursiveCalc(typ)
End Sub
Private Sub RecursiveCalc(ByVal typ As Type)
_ListType.Add(typ)
If typ.BaseType IsNot Nothing Then
RecursiveCalc(typ.BaseType)
End If
End Sub
End Class
Private Shared _ListType As List(Of Type)
Private Function GetListClassAncestryByShared(ByVal typ As Type) As List(Of Type)
If _ListType Is Nothing Then ' callers must set this to null when done
_ListType = New List(Of Type)
End If
_ListType.Add(typ)
If typ.BaseType IsNot Nothing Then
GetListClassAncestryByShared(typ.BaseType) ' recur
End If
Return _ListType
End Function
Private Function GetListClassAncestryByExtraParam(ByVal typ As Type, ByVal lstTypes As List(Of Type)) As List(Of Type)
While typ <> Nothing
lstTypes.Add(typ)
typ = typ.BaseType
End While
Return lstTypes
End Function
Private Function GetListClassAncestryOptParam(ByVal typ As Type, Optional ByVal lstTypes As List(Of Type) = Nothing) As List(Of Type)
If lstTypes Is Nothing Then
lstTypes = New List(Of Type)
End If
lstTypes.Add(typ)
If typ.BaseType IsNot Nothing Then
GetListClassAncestryOptParam(typ.BaseType, lstTypes) ' recur
End If
Return lstTypes
End Function
Private Function GetListClassAncestryByLoop(ByVal typ As Type) As List(Of Type)
Dim lst = New List(Of Type)
While typ <> Nothing
lst.Add(typ)
typ = typ.BaseType
End While
Return lst
End Function
End Class
</Sample>
Comments
- Anonymous
July 06, 2011
It would be nice if you specified this is a .Net Framework 4.0 only sample.