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     Wend     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  

Learning Apps Script, (and transitioning from VBA) are covered comprehensively in my book.