Suggestions Sample File
Recursion


1. Introduction

2. Recursion illustrated

3. Algorithm

4. Recursion

5. Macro to create combinations
5.1 Step by step
5.2 Stop criterion
5.3 Storing results
5.4 Complete procedure

6. Call
6.1 Inventory of Subfolders
6.2 Permutations

7. Sample file

1. Introduction

An underexposed technique in VBA is recursion. It's a theme I don't see in manuals. Let alone a clear explanation of the technique, when it can be used and what the pitfalls are.
The technique is rather abstract.
Here I will therefore describe the recursion technique using an example.
This example is based on the 'challenge' that Jan Karel Pieterse introduced in 2019 on his website challenge.
. What surprised me was that none of the VBA-transmitters had made use of recursion, while in this case it's very obvious.
The solutions provided provide a good opportunity to illustrate the advantages of recursion compared to the solutions submitted.

2. Illustration with an example

The question is: how can we create a VBA routine that produces all (unique) combinations of 5 elements from a set of 10 elements? The characteristics of a combination:
- a combination contains only unique elements (so no repetitions)
- the order of the elements in a combination does not matter. The following combinations are considered identical: ABCDE, ABCED, ABDCE... EDCBA

How many possible combinations are there?
You can break your head to calculate the number of combinations, but Excel already has a worksheet formula for that:
Combin(population size, combination size)

If you want to know the number of combinations of 5 elements from a group of 10, then the formula =Combin(10;5) gives you the answer.

3. Algorithm

In this case, we are not going to try to find a mathematical solution to the problem.
In other words, we are not going to calculate which elements per each possible combination should occur in which order in that combination.
The proposals received at the request of JKP all use a 'rotation method': depending on the elements of the onset of a combination, new, unique elements are added.
The clearest illustration of this is the VBA code of Garys Student:
Sub kombo5_10()
Dim arr, Z As Long, c As Long, d As Long
Dim e As Long, f As Long, g As Long

arr = Range("A1:J1").Value
Z = 2
For c = 1 To 6
For d = c + 1 To 7
For e = d + 1 To 8
For f = e + 1 To 9
For g = f + 1 To 10
Cells(z, 1) = arr(1, c) & "," & arr(1, d) & "," & arr(1, e) & "," & arr(1, f) & "," & arr(1, g)
Z = Z + 1
Next g
Next f
Next e
Next d
Next c
End Sub
- in Range("A1:J1) are the numbers 1 to 10
- because it concerns the combinations of 5 elements, 5 nested loops are needed to make 1 full combination
- the variable z determines in which row in column A the combination is written
- the value of the maximum value of each loop is 'fixed' encoded

Improvements

- each combination is written separately to the worksheet; this can be done more efficiently with an Array variable
. - the code is not flexible and only works for the number of combinations of 5 elements from a population of 10 items
- for each element of the combination there is a separate for... next loop. This is confusing when more elements are involved.

4. Recursion

Recursion is the 'self-calling' of a VBA procedure (macro or function).
With recursion you can run through a large number of loops by letting the macro call itself at all times.

When do you use recursion ?
- If there are many nested loops, or
- If it is not known in advance how many loops will have to be passed through.
- The condition is that the loops are almost identical

A recursive macro
- contains parameters/arguments.
With arguments (parameters) you can give the macro values for the calculation in the macro.

- contains a condition to stop calling itself.
If that condition is missing, the code will go into an endless loop, until no more working memory is available and the program aborts.

- contains code to store the results of the calculation (e.g. in a variable, a workbook, a file, etc.)

5. Recursive macro for unique combinations

By means of a procedure to produce unique combinations, all elements of recursion will be covered.

Basic form of a recursive macro
Sub M_comb(c00, y, t)
for j = y + 1 to t
M_comb c00 & j & "_", y + 1, t + 1
next
End sub
Because a macro with arguments (in this case c00, y and t) cannot start itself, we need another macro as a start macro.
Sub M_snb()
M_comb "", -1, 5
End sub
explanation of the arguments:
c00 is a variable for the provisional values per loop.
After the
1st loop: "0_"
2nd loop: "0_1_"
3rd loop: "0_1_2_"
4th loop: "0_1_2_3_"

y is the lower limit for starting the loop in the recursive macro. In the code of Garys Student we saw that every next loop has to start with a value 1 higher than the iterator of the previous loop.
We do this by adding 1 to the passed value
For j = y + 1 To
t is the upper limit of the loop in the recursive macro.
In the code of Garys Student, we saw that each subsequent loop must end with a value 1 higher than the upper limit of the previous loop.
When calling the macro, the last argument is the variable t + 1.
M_comb c00 & j & "_", y + 1, t + 1

5.1 step by step

Start the recursion macro with three arguments

c00 contains the intermediate result; at the start c00 is an empty text string

y is the value of the lower limit, the value -1
the recursion macro adds 1 to the transmitted lower boundary variable.
The lower limit of variable j in the first loop is therefore 0.

t is the value of the upper limit; in this case it is the length (the number of elements) of the combination (in this example 5)
Every next time the macro is called, the value t is increased by 1.

Start call
Sub M_snb()
M_comb "", -1, 5
End sub
1st loop
Sub M_comb("", -1, 5)
For j = 0 To 5
M_comb "0_", 0, 6
Next
End Sub
2nd loop
Sub M_comb("_0", 0, 6)
For j = 1 To 6
M_comb "0_1_", 1, 7
Next
End Sub
3rd loop
Sub M_comb("_0_1", 1, 7)
For j = 2 To 7
M_comb "0_1_2_", 2, 8
Next
End Sub
etc.

5.2 Stop criterion

The recursive macro still lacks a stop criterion.
If a combination contains 4 elements, it is the end of the loop because the addition of the iterator variable will result in a 5-element string.
Then the recursive macro is no longer called.

The length of the combination ( = the number of elements in the combination) is determined by splitting the text sequence c00 into an Array.
The split separator is the underscore "_".
The result of the split of a text line is an Array with lower limit (Lbound) 0. If the upper limit of the splitted array is 3, the array contains 4 elements.

in VBA:
Sub M_comb(c00, y, t)
For j = y + 1 To t
If Ubound(Split(c00,"_")) = 3 Then
c00 = c00 & j & "_"
Else
M_comb c00 & j & "_", y + 1, t + 1
End if
Next
End Sub

5.3 Storing results

We want to save the results in the worksheet.
The most convenient way to do this is using a 2-dimensional Array variable.
While running the macro we store all results in it.
Finally, we write that storage variable to the worksheet in 1 go.
The fewer read and write operations to a worksheet, the faster the overall macro will be.

Since we use 2 macros, we need an Array variable that is accessible for all procedures (macros, functions, events) in the same module.
In this case we use the macromodule of the worksheet in which we work for the start macro, the recursive macro and the storage Array variable.
At the beginning of the module we declare the Array variable as
Dim sp
or
Private sp
Next, we have to make the size of the Array variable large enough to contain all possible unique combinations.
In the start macro we use the command Redim to do this. Because Excel has a spreadsheet function for calculating the number of possible combinations, we use it to determine the size of the storage variable.
Dim sp
Sub M_snb()
Redim sp(Application.Combin(10,5),0)
M_comb "", -1, 5
End Sub
Since each combination result has to be placed in a separate element of the Array variable, we need a counter that keeps track of how many combinations the Array-variable sp already contains.
Each time the Array variable gets a new combination, the counter goes up by 1.
In this example, we will use the variable r to do this.
Just like the variable sp, we declare this variable r at module level.

in VBA:
Sub M_comb(c00, y, t)
For j = y + 1 to t
If Ubound(Split(c00,"_")) = 3 Then
sp(r,0)= c00 & j & "_"
r = r + 1
Else
M_comb c00 & j & "_", y + 1, t + 1
End If
Next
End Sub
If the storage variable contains all the results, we use the start macro to write the storage variable to the worksheet.
Of course we don't use the recursion macro, since only after its last run the array variable is completely filled.
Dim sp, r

Sub M_snb()
Redim sp(Application.Combin(10,5),0)
M_comb "", -1, 5
Sheet1.Cells(1).Resize(Ubound(sp)+1) = sp
End Sub

5.4 Complete procedure

The complete recursion procedure looks as follows:

1 storage variable
1 counter variabele
1 start and storing macro
1 recursion macro
Dim sp, r

Sub M_snb()
Redim sp(Application.Combin(10,5),0)
r = 0

M_comb "", -1, 5

Sheet1.Cells(1).Resize(Ubound(sp)+1) = sp
End Sub

Sub M_comb(c00, y, t)
For j = y + 1 To t
If Ubound(Split(c00,"_")) = 3 then
sp(r,0) = c00 & j & "_"
r = r + 1
Else
M_comb c00 & j & "_", y + 1, t + 1
End If
Next
End Sub
Advantages:
- the code is independent of the size of the population
- the code is independent of the size of the combination
- the code has maximum flexibility
- the code needs no maintenance
- the code is limited: 8 lines of VBA code
- the interaction with the workbook is minimal
- the execution of the macro is very fast

6. Call for examples

Since there is little documentation about recursion, I would like to receive examples of recursion.
I will then place these in this webpage (with correct mentioning of its source).
Please use the link Suggestions.
The greater the variety of examples to study the easier it is to study and apply the principle of recursion yourself.
Below 2 examples.

6.1 Inventory of Subfolders

Because the number of elements is unknown beforehand, we use a dynamic Array sp().
The command "Redim Preserve" enlarges the Array by 1 element when a new item is found.
Every found item will be stored in the last position of the Array-variable.
That's why we don't need a counter-variable in this case.

The collections of (sub)folders are finite
As soon as the last item of a collection is found, the recall of the recursion macro stops.
That's why we do not need an explicit stop criterion in this case.

Dim fs, sp()

Sub M_snb()
Set fs = CreateObject("scripting.filesystemobject")
ReDim sp(0)

M_folder Application.DefaultFilePath

MsgBox "Number of subfolders in " & Application.DefaultFilePath & " : " & UBound(sp) + 1 & vbLf & Join(sp, vbLf)
End Sub

Sub M_folder(c00)
For Each it In fs.GetFolder(c00).subfolders
ReDim Preserve sp(UBound(sp) + 1)
sp(UBound(sp)) = it.Path

M_folder it.Path
Next
End Sub

6.2 Permutations

The VBA code in this example is based on that of RebMog.

The code calculates all possible permutations of y elements.
The results end up in an Array variable sp().
The example uses elements from the "0123456789" series of digits.
This allows permutations to start with a 0.
Excel automatically converts strings of numbers into a number.
A permutation so loses a 0 at its beginning.
The declaration of the Array-variable of the type 'String' prevents this.

Dim sp() as String, p

Sub M_snb()
y = 7
ReDim sp(Application.Fact(y), 0)
p = 0

M_perm "", Left("0123456789", y)

Sheet1.Cells(1, 5).Resize(UBound(sp) + 1) = sp
End Sub

Sub M_perm(c00, c01)
If Len(c01) = 1 Then
sp(p, 0) = c00 & c01
p = p + 1
Else
For j = 1 To Len(c01)
M_perm c00 & Mid(c01, j, 1), Left(c01, j - 1) & Right(c01, Len(c01) - j)
Next
End If
End Sub

7. Sample file

In the example file, the recursion macro for generating unique combinations is integrated with worksheet interaction.

Explanation

- cell C1: choose the size of the population; the 'Worksheet_Change' event adjusts the options in cell C2 for the size of the combination
- cell C2: Make a choice for the size of the combination
- cell C3: the formula = Combin(C1;C2) calculates the number of possible combinations
- the event code 'Worksheet_Change' starts the recursion macro 'M_comb'.
- the event code 'Worksheet_Change' writes the results into Table 'T_00' from cell D9 onwards
- cell C4: by double-clicking you can choose to display the combinations as number sequences or as items from the table 'labels' in Range B10:B35

- cell B5: is linked to cell C4: use of labels/numbers
- cell B6: is linked to cell C1: the size of the population
- cell B7: is linked to cell C2: the size of the combination
- cell B8: contains the number 1 as the counter for the storage variable sp

- the area A5:B..n serves as an area to determine the size of the storage variable sp
- the first column is used to store the results of the macro, the second column to read the basic parameters for the macro.