VBA voor smarties: Recursie

Recursie

Combinaties
Sudoku

1. Inleiding

2. Illustratie met voorbeeld

3. Algoritme

4. Recursie

5. Macro voor combinaties
5.1 Voorbeelddoorloop
5.2 Stopcriterium
5.3 Resultaten opslaan
5.4 Totale procedure

6. Oproep
6.1 Subfolderoverzicht
6.2 Permutaties

7. Voorbeeldbestand

1. Inleiding

Een onderbelichte techniek in VBA is 'recursion'.
Het is een thema, dat ik in handboeken niet tegenkom.
Laat staan dat er een heldere uitleg bestaat over de techniek, wanneer die gebruikt kan worden en wat de valkuilen zijn.
De techniek is tamelijk abstract.
Hier zal ik de recursion-techniek daarom beschrijven aan de hand van een voorbeeld.
Dit voorbeeld is gebaseerd op de 'uitdaging' die Jan Karel Pieterse in 2019 introduceerde op zijn website challenge.
Wat mij nl. verbaasde was dat geen van de VBA-inzenders gebruik had gemaakt van recursie, terwijl dat in dit geval erg voor de hand ligt.
De aangereikte oplossingen bieden een mooie gelegenheid om de voordelen van recursion ten opzichte van de ingezonden oplossingen te illustreren.

2. Illustratie met een voorbeeld

De vraag is: hoe kunnen we een VBA-routine maken die alle (unieke) combinaties van 5 elementen uit een verzameling van 10 elementen produceert?
De kenmerken van een combinatie:
- een combinatie bevat alleen maar unieke elementen (geen herhalingen dus)
- de volgorde van de elementen in een combinatie doet er niet toe. De volgende combinaties worden als identiek beschouwd : ABCDE, ABCED, ABDCE... EDCBA

Hoeveel mogelijke combinaties zijn er?
Je kunt je het hoofd breken om het aantal combinaties te berekenen, maar Excel heeft daarvoor al een werkbladformule:
Combin(populatie-omvang, combinatie-omvang)

Wil je het aantal combinaties weten van 5 elementen uit een groep van 10, dan geeft de formule =Combin(10;5) je het antwoord.

3. Algoritme

We gaan in dit geval niet proberen om een wiskundige oplossing voor het vraagstuk te vinden.
We gaan met andere woorden niet berekenen welke elementen per iedere mogelijke combinatie in welke volgorde in die combinatie moeten voorkomen.
De voorstellen die op de vraag van JKP binnenkwamen maken allemaal gebruik van een 'rotatiemethode': afhankelijk van de elementen van de aanzet van een combinatie worden nieuwe, unieke elementen toegevoegd.
De duidelijkste ilustratie daarvan is de VBA-code van 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) staan de getallen 1 t/m 10
- omdat het om de combinaties van 5 elementen gaat zijn 5 geneste loops nodig om 1 volledige combinatie te maken
- de variabele z bepaalt in welke rij in kolom A de combinatie wordt geschreven
- de waarde van de maximumwaarde van iedere lus wordt 'hard' gecodeerd

Verbeteringen

- iedere combinatie wordt afzonderlijk naar het werkblad geschreven; dat kan efficiënter met een Array-variabele
- de code is niet flexibel en werkt alleen voor het aantal combinaties van 5 elementen uit een populatie van 10 items
- voor ieder element van de combinatie bestaat een afzonderlijke for ... next loop. Dat is onoverzichtelijk als het om meer elementen gaat.

4. Recursie

Recursie is het 'zichzelf oproepen' van een VBA-procedure (macro of funktie).
Met recursie kun je een groot aantal lussen laten doorlopen door de macro steeds zichzelf te laten aanroepen.

Wanneer gebruik je recursie ?
- Als er sprake is van veel geneste lussen, of
- Als vooraf onbekend is hoeveel lussen er doorlopen moeten worden.
- Voorwaarde is dat de lussen nagenoeg identiek zijn.

Een recursiemacro
- bevat parameters/argumenten.

Met argumenten (parameters) kun je aan de macro waarden meegeven voor de berekening in de macro.

- bevat een voorwaarde om te stoppen zichzelf aan te roepen.

Als die voorwaarde ontbreekt raakt de code in een oneindige lus, totdat er geen werkgeheugen meer beschikbaar is en het programma afbreekt.

- bevat code om de resultaten van de berekening/bewerking op te slaan (bijv. in een variabele, een werkboek, een bestand, etc.)

5. Recursieve macro voor unieke combinaties.

Aan de hand van een procedure om unieke combinaties te produceren komen alle elementen van recursie aan bod.

Basale vorm van een recursieve macro

Sub M_comb(c00, y, t)

for j = y + 1 to t

M_comb c00 & j & "_", y + 1, t + 1

End sub

Omdat een macro met argumenten (in dit geval c00, y en t) zichzelf niet kan starten hebben we een andere macro nodig als startmacro.

Sub M_snb()

M_comb "", -1, 5

End sub

toelichting op de argumenten:
c00 is een variabele voor de voorlopige waarden per lus.
Na de
1e lus: "0_"
2e lus: "0_1_"
3e lus: "0_1_2_"
4e lus: "0_1_2_3_"

y is de ondergrens voor de start van de lus in de recursieve macro.
In de code van Garys Student zagen we dat iedere volgende lus met 1 waarde hoger moet beginnen dan de iterator van de voorgaande lus.
Dat doen we door aan de doorgegeven waarde 1 toe te voegen

For j = y + 1 To

t is de bovengrens van de lus in de recursieve macro.
In de code van Gary Student zagen we dat iedere volgende lus met 1 waarde hoger moet eindigen dan de bovengrens van de voorafgaande lus.
Bij het aanroepen van de macro geven we als laatste argument dan ook de variabele t + 1 mee.

M_comb c00 & j & "_", y + 1, t + 1

5.1 voorbeelddoorloop

Start de recursie-macro met drie argumenten

c00 bevat het tussenresultaat; bij de start is c00 een lege tekstreeks

y is de waarde van de ondergrens, de waarde -1

de recursie-macro telt bij de doorgegeven ondergrensvariabele 1 op.
De ondergrens van variabele j in de eerste lus is dus 0.

t is de waarde van de bovengrens; in dit geval is dat de lengte (het aantal elementen) van de combinatie (in dit voorbeeld 5)

Iedere volgende keer dat de macro aangeroepen wordt, wordt de waarde t met 1 verhoogd.

Start-aanroep

Sub M_snb()

M_comb "", -1, 5

End sub

1e lus

Sub M_comb("", -1, 5)

For j = 0 To 5

M_comb "0_", 0, 6

End Sub

2e lus

Sub M_comb("_0", 0, 6)

For j = 1 To 6

M_comb "0_1_", 1, 7

End Sub

3e lus

Sub M_comb("_0_1", 1, 7)

For j = 2 To 7

M_comb "0_1_2_", 2, 8

End Sub

etc.

5.2 Stopcriterium

Aan de recursieve macro ontbreekt nog een stopcriterium.
Als een combinatie 4 elementen bevat is dat het einde van de lus.
Want toevoeging van de iteratorvariabele levert dan een tekenreeks met 5 elementen op.
Vervolgens wordt de recursiemacro niet meer aangeroepen.

De lengte van de combinatie ( = het aantal elementen in de combinatie) bepalen we door de tekstreeks c00 in een Array te splitsen.
Het splitsingsteken is de underscore "_".
Het resultaat van de splitsing van een tekstreeks is een Array met ondergrens 0.
Als de bovengrens van de array 3 is, bevat de array 4 elementen.

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

End Sub

5.3 Resultaten opslaan

De resultaten willen we opslaan in het werkblad.
De handigste vorm daarvoor is een 2-dimensionele Array variabele.
Tijdens de macro bewaren we daarin alle resultaten.
Tenslotte schrijven we die opslagvariabele in 1 keer naar het werkblad.
Hoe minder lees- en schrijfbewerkingen er naar een werkblad plaatsvinden hoe sneller de totale macro.

Omdat we gebruik maken 2 macro's hebben we een Array-variabele nodig die benaderbaar is voor alle procedures (macro's, funkties, gebeurtenissen) in dezelfde module.
In dit geval gebruiken we de macromodule van het werkblad waarin we werken voor de startmacro, de recursieve macro en de opslag Array variabele.
Aan het begin van de module declareren we de Array variabele dan ook als

Dim sp

Private sp

Vervolgens moeten we de omvang van de Array-variabele groot genoeg maken om daar alle mogelijke unieke combinaties in te kunnen zetten.
Daarvoor gebruiken we in de startmacro de opdracht Redim.
Omdat Excel een werkbladfunktie heeft voor de berekening van het aantal mogelijke combinaties gebruiken we die om de omvang van de opslag-variabele vast te leggen.

Dim sp
Sub M_snb()

Redim sp(Application.Combin(10,5),0)
M_comb "", -1, 5

End Sub

Omdat ieder combinatie-resultaat in een afzonderlijk element van de Array variabele gezet moet worden hebben we een teller nodig die bijhoudt hoeveel combinaties Array-variable sp al bevat.
Iedere keer als de Array-variabele een nieuwe combinatie krijgt gaat de teller met 1 omhoog.
In dit voorbeeld gebruiken we daarvoor de variable r.
Net zoals de variabele sp declareren we deze variabele r op modulenivo.

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

End Sub

Als de opslagvariabele alle resultaten bevat gebruiken we de startmacro om de opslagvariabele naar het werkblad te schrijven.
Natuurlijk gebruiken we daarvoor niet de recursiemacro.
Dan zou nl. net zo vaak naar het werkblad worden geschreven als het aantal keren dat de recursiemacro loopt.

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 Totale procedure

De totale recursieprocedure bestaat nu uit:

1 opslagvariabele
1 tellervariabele
1 start- en opslagmacro
1 recursiemacro

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

End Sub

Voordelen:
- de code is onafhankelijk van de omvang van de populatie
- de code is onafhankelijk van de omvang van de combinatie
- de code is maximaal flexibel
- de code vergt geen onderhoud
- de code is beperkt: 8 regels VBA-code
- de interaktie met het werkboek is minimaal
- de uitvoering van de macro is razendsnel

6. Oproep

Omdat er weinig documentatie bestaat over recursie hierbij een oproep om voorbeelden daarvan naar mij op te sturen.
Die plaats ik dan vervolgens in deze webpagina (met bronvermelding).
Gebruik daarvoor svp de link Suggesties.
Hoe meer verschillende voorbeelden er zijn, hoe gemakkelijker je het principe van recursie kunt bestuderen en zelf toepassen.
Hieronder 2 voorbeelden.

6.1 Subfolderoverzicht

Omdat het aantal elementen vooraf onbekend is gebruiken we een dynamische Array sp().
De opdracht "Redim Preserve' vergroot de Array met 1 element als een nieuw item is gevonden.
Ieder gevonden item komt daardoor in de laatste positie van de Array-variable terecht.
Daarom hebben we in dit geval geen teller-variabele nodig.

De verzamelingen (Collections) van (sub)folders zijn eindig.
Zo gauw het laatste item van een collection is gevonden stopt het aanroepen van de recursiemacro.
Daarom hebben we in dit geval geen expliciet stopcriterium nodig.

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

End Sub

6.2 Permutaties

De code in dit voorbeeld is ontleend aan die van RebMog.

De code berekent alle mogelijke permutaties van y elementen.
De resultaten komen terecht in een Array variabele sp().
Het voorbeeld maakt gebruik van elementen uit de cijferreeks "0123456789".
Daardoor kunnen permutaties met een 0 beginnen.
Excel converteert getallenreeksen automatisch naar een getal.
Een permutatie verliest doordoor de 0 aan het begin.
De declaratie van de Array-variable van het type 'String' verhindert dat.

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)

End If

End Sub

7. Voorbeeldbestand

In het voorbeeldbestand is de recursieve macro voor het genereren van unieke combinaties geïntegreerd met werkbladinteraktie.

Toelichting:

- cel C1: maak een keuze voor de omvang van de populatie; het werkblad past de opties in cel C2 voor de omvang van de combinatie aan
- cel C2: maak een keuze voor de omvang van de combinatie
- cel C3: de formule = Combin(C1;C2) berekent het aantal mogelijke combinaties
- de gebeurteniscode 'Worksheet_Change' start de recursiemacro 'M_comb'.
- de gebeurteniscode 'Worksheet_Change' schrijft de resultaten in Tabel 'T_00' vanaf cel D9
- cel C4: door te dubbelklikken kun je kiezen voor weergave van de combinaties als getallenreeksen of als items uit de tabel 'labels' in Range B10:B35

- cel B5: is gekoppeld aan cel C4: gebruik van labels/getallen
- cel B6: is gekoppeld aan cel C1: de omvang van de populatie
- cel B7: is gekoppeld aan cel C2: de omvang van de combinatie
- cel B8: bevat het getal 1 als teller voor de opslagvariabele sp

- het gebied A5:B..n fungeert als gebied om de omvang van de opslagvariabele sp te bepalen;
- de eerste kolom dient om de resultaten van de macro op te slaan, de tweede kolom om de basisparameters voor de macro in te lezen.