Getting started with recursion

What can you learn here ?
  • Recursion coding techniques
  • When to use recursion
  • Dealing with tree structures


Usually recursion is considered to be a rather advanced topic, but actually it's pretty straightforward - just easy to get it wrong. Object orientation and the increased use of classes and  tree structures in everyday coding have made the use of recursion much easier to implement, and much more necessary to use.

What is recursion

Recursion is where a procedure calls itself repeatedly. Normally recursion can be mimicked by the use of loops, but this kind of looping coding can quickly become unintelligible when dealing with structures of indeterminate depth and complexity. 

Replacing looping with recursion

One of the easiest ways of learning recursion concepts is to replace the function of a simple loop with a recursive function call. This does not mean that it is wise to implement loops this way, but simply that it is a straightforward way to 'get started'. Consider this loop:

    Dim loops As Long
    loops = 0
    While Rnd() < 0.95
        loops = loops + 1
    MsgBox ("finished loop version " & CStr(loops))

This will count how many times a random number returns a value less that .95 and stop when > .95 is reached. Pretty pointless, but a good illustration of a loop where the upper limit is not known.

Now look at the same thing implemented as a recursive function. First the main code would look like this

MsgBox ("finished recursive version " & CStr(recurseTillRandom()))

Now the function

Function recurseTillRandom(Optional loops As Long = 0) As Long
    If Rnd() < 0.95 Then loops = recurseTillRandom(loops + 1)
    recurseTillRandom = loops
End Function

This will keep calling itself until a random number greater than .95 is reached, and the counting is done by calling itself with an ever increasing count. Eventually the condition is satisfied and the function returns the value of its argument. It's that simple. Make sure you get how this would play out before continuing. If necessary download the get started series workbook, set a breakpoint in the function, and step through it. Once you have it, you will have conquered the concept of recursion. 

Navigating tree structures

One of the most common uses of recursion is to get around tree structures. You should take a look at Getting Started with Classes to see the details of the class we are going to use to illustrate. It looks like this

Option Explicit
Private pKey As Long
Private pName As String
Private pChildren As Collection
Public Property Get Key() As Long
    Key = pKey
End Property
Public Property Get Name() As String
    Name = pName
End Property
Public Property Get Children() As Collection
    Set Children = pChildren
End Property
Public Property Let Key(p As Long)
    pKey = p
End Property
Public Function Init(k As Long, sName As String) As cMyClass
    pKey = k
    pName = sName
    Set pChildren = New Collection
    Set Init = Me
End Function

The objective is to navigate through the children structure and print the details using recursion. Here is the test procedure

Sub testChildrenRecurse()
    Dim mroot As cMyClass, mc As cMyClass
    Set mroot = New cMyClass
    With mroot
        .Init 100, "bill"
        Set mc = New cMyClass
        .Children.add mc.Init(200, "janet")
        Set mc = New cMyClass
        .Children.add mc.Init(201, "john")
        Set mc = New cMyClass
        .Children.add mc.Init(202, "mary")
        Set mc = New cMyClass
        .Children(2).Children.add mc.Init(300, "tom")
        Set mc = New cMyClass
        .Children(2).Children.add mc.Init(301, "fred")

    End With
    printChildren mroot
End Sub

and here is how to go through the tree structure, indenting as we go. 

Sub printChildren(mroot As cMyClass, Optional level As Long = 0)
    Dim mc As cMyClass
    Debug.Print Space(level); mroot.Name; " has "; mroot.Children.Count; " children"
    For Each mc In mroot.Children
        printChildren mc, level + 2
    Next mc
End Sub

This produces this output, all nicely indented for each generation

bill has  3  children
  janet has  0  children
  john has  2  children
    tom has  0  children
    fred has  0  children
  mary has  0  children