What is Recursion?
The dictionary definition of Recursion says it all:
Recursion (n.) - see under "Recursion"
And if you didn't get (or like) that joke, here's a real definition: recursive programming is when you write a program which calls itself.
In practice there are few occasions when you'll actually use recursion - but when you do need it, it's nearly indispensable! The examples this tutorial will show are:
Example | Notes |
|---|
Folder contents | Recursively looping over folders and subfolders |
Creating breadcrumbs | Creating menu breadcrumbs for hierarchical data |
Calculating a factorial | Calculating the factorial of a number |
Of these, it would be much harder to write the first two examples without using recursion.
Example 1 - Listing Files: Purpose of Program
The aim of this exercise is to list out the name and path of every single file in a folder or in any of its subfolders. Here's what we'll be aiming to list:
We'll aim to print out the names of all files in the Wise Owl folder, and in all of its subfolders (however many levels nested these may be).
Part of the output our program could produce in the Immediate window might look like this:
The recursive program will list out all files found in all folders.
Example 1 - Listing Files: The Subroutine to List Out a Folder's Files
At its heart, our program will contain a subroutine which lists out all of the files in a given folder, and then goes on to loop over all of that folder's subfolders:
Sub ListFiles(fol As Folder)
Dim fil As File
Dim subfol As Folder
On Error Resume Next
If fol.Files.Count > 0 Then
Debug.Print ""
Debug.Print "FILES IN " & UCase(fol.Path); ""
Debug.Print ""
End If
For Each fil In fol.Files
Debug.Print fil.Path
Next fil
For Each subfol In fol.SubFolders
ListFiles subfol
Next subfol
On Error GoTo 0
End Sub
I've shown the most important line in bold: the one which calls the subroutine ListFiles again, using a subfolder of the main folder as its argument.
Example 1 - Listing Files: The Routine to Start the Process
Finally, we need the code which will start the process off, by calling the ListFiles routine shown above with a folder as an argument:
Option Explicit
Dim fso As New FileSystemObject
Sub StartProcess()
Dim fol As Folder
Set fol = fso.GetFolder("C:\Wise Owl\")
ListFiles fol
End Sub
If you run the StartProcess routine above, it should list out all of the files in the Wise Owl folder and all of its subfolders!
Note that stepping through programs like this can be a nightmare, since it is hard to know which instance of the ListFiles routine you are currently debugging.
Example 2 - Hierarchical Data: Purpose of Program
For the purposes of this tutorial, I've defined hierarchical data as any database where each record points to its immediate parent in the hierarchy, which is stored in the same table. Here's an example, which should make things clearer:
For this list of employees, the record for each person shows who is their immediate line manager. So Wayne Rooney is managed by Basil Brush (id 5), who is managed by Simon Templar (id 1), who is managed by Alastair Campbell (id 6).
Storing data like this is an elegant and compact way to store any hierarchy, but it's hard to get the information back out without recursion.
Example 2 - Hierarchical Data: Breadcrumbs
Breadcrumbs provide an audit trail of where you are in a website or system. For example, if you're trying to buy a spare wheel for your bicycle, the trail might read:
Sport and Leisure --> Cycling --> Parts --> Wheels and tyres
For our example above, we want to produce the following breadcrumbs:
Alastair Campbell --> Simon Templar --> Basil Brush --> Wayne Rooney
Here is a program which would do the trick. To keep it simple, I've omitted any checks or error trapping:
Option Explicit
Dim BreadCrumbs As String
Sub ShowBreadcrumbs()
Dim Person As String
BreadCrumbs = ""
AccumulateBreadCrumbs 4
MsgBox BreadCrumbs
End Sub
Sub AccumulateBreadCrumbs(Id As Integer)
Columns("A").Find(What:=Id, Lookat:=xlWhole).Select
If Len(BreadCrumbs) > 0 Then BreadCrumbs = " --> " & BreadCrumbs
BreadCrumbs = ActiveCell.Offset(0, 1).Value & BreadCrumbs
Dim ManagerId As Integer
ManagerId = ActiveCell.Offset(0, 2).Value
If ManagerId = 0 Then
Exit Sub
Else
AccumulateBreadCrumbs ManagerId
End If
End Sub
The critical line is shown in bold above: this is the one which calls the macro recursively:
AccumulateBreadCrumbs ManagerId
When you run the ShowBreadcrumbs subroutine above, you should get:
The output from the program above shows the accumulated breadcrumbs.
Easy with recursion - very hard without it!
Example 3 - Factorials: Purpose of Program
The factorial of a number is written (in the UK at any rate) as n!. For example:
Notice that for any n:
To the experienced programmer, this is crying out for a program which will call itself recursively.
Example 3 - Factorials: Our Code
The program below will show one of two things:
 |  |
Output if the factorial isn't too big | Output if the number is too large |
Here is the suggested program. First we set some global variables (including the seed whose factorial we'll calculate):
Option Explicit
Dim CurrentFactorial As Long
Dim IfOverflow As Boolean
Const Seed As Integer = 10
Next, we'll write our subroutine which calls itself recursively:
Sub GetFactorial(n As Integer)
If IfOverflow Then Exit Sub
On Error GoTo Overflow
If n <= 1="">Then Exit Sub
CurrentFactorial = CurrentFactorial * n
GetFactorial (n - 1)
Exit Sub
Overflow:
IfOverflow = True
End Sub
The important line is the one I've put in bold: the GetFactorial subroutine calls itself, with a number one less each time.
Finally, we need to write a program to call the GetFactorial subroutine in the first place, and to display its result:
Sub ShowFactorials()
IfOverflow = False
CurrentFactorial = 1
Call GetFactorial(Seed)
If IfOverflow Then
MsgBox "Too large a number generated - try something smaller"
Else
MsgBox "Factorial of " & Seed & " is " & CurrentFactorial
End If
End Sub
When you run this last subroutine, you'll see the factorial of the number you chose as a seed!
