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.