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