Recursive Code

[Myles]

Hi all,

I am re-visiting my initial query (lost in traffic) hoping this time
someone will kindly oblige me. In my desperation to -understand- the
mechanics of this code credited to Tom Ogilvy , I threw in MsgBoxes in
strategic places so to trap and monitor the changing values of the
respective variables and not least the worksheet output. The more
trappings I did, the more I became mystified. Assuming activecell is
A1, and using n = 9 and m = 3, the code populates Column A with all the
84 possible combinations - selecting 3 items at a time from 1,2,3 ...
9.

Sub Combinations()
Dim n As Integer, m As Integer
numcomb = 0
'n = InputBox("Number of items?", , 10)
'm = InputBox("Taken how many at a time?", , 3)
n=9
m=3

com n, m, 1, "'"
End Sub

'Generate combinations of integers k..n taken m at a time, recursively
Sub com(ByVal n%, ByVal m%, ByVal k%, ByVal s as String)
If m > n - k + 1 Then Exit Sub
If m = 0 Then
ActiveCell = s
ActiveCell.Offset(1, 0).Select
MSGBOX M & \" \" & K & \" \" & S
Exit Sub
End If
com n, m - 1, k + 1, s & k & " "
MSGBOX M & \" \" & K & \" \" & S
com n, m, k + 1, s
MSGBOX M & \" \" & K & \" \" & S
End Sub


Myles

 

[Peter T]

Hi Myles,

A Recursive procedure calls itself passing same set of arguments to process.
Typically something like this -

'code
If not done enough then
'code
call myself again
End if

or in your example

If done enough then
'code
exit Sub
End if
'code
call myself again

Each new instance of the procedure starts afresh with it's own set of any
declared variables, ie values don't persist into the next level unless
declared as Static.

Need to ensure eventually there will be no need to 'call myself again' or
you'll run out of stack space.

A simplistic and contrived example, pads a string a single "A" until the
required length is built -

Sub testRecursive()
Dim s As String
s = "w"
recursive s, 5
MsgBox s
End Sub

Sub recursive(sIn As String, nLen As Long, _
Optional ByVal nLevel As Long)
Dim sp As String

nLevel = nLevel + 1
sp = Space(nLevel)
Debug.Print sp & "Enter" & nLevel, sIn

If Len(sIn) < nLen Then
sIn = sIn & "A"
recursive sIn, nLen, nLevel
End If

Debug.Print sp & "Exit" & nLevel, sIn
End Sub

Press ctrl-g to see the debug results in the intermediate window.

In the example you posted you could pass the range (eg activecell) and an
offset counter to increment as arguments which would avoid the need to
select the next cell each time.

Regards,
Peter T

 

[Myles]

Many thanks Peter for your incisive response.

Given that recursive codes "recoil" upon themselves, ever lookin
inwards, how would you then explain the piggy-back instance:

Combin n m-1 k+1 s&" " & k
Combin n m k+1 & s

I would imagine that the first code will be evaluated for th
diminishing vales of m till m=0. At this point in time, one set (of
values) -using my example of 3 Combin 9-will have been amassed an
deposited in the activecell. Next, the second stanza Combin n m k+1
s is pressed into service and since it does have the first stanz
embedded in its bowel, another cycle is commisioned. The puzzle is tha
while the first pass yields the combination set 1 2 3, the secon
delivers 1 2 4 (the third 1 2 5 and so on). Assuming that th
inception of any call comes with fresh and new set of intial values
in this case n=9, m=3, k =1 and s the original value " " . Thi
scenario should reproduce the same result 1 2 3 as before. I am at los
to account for the incrememtal 1 2 4?

I will welome any light shed?

Meanwhile, I walked through your example code and found the steps an
results logical. No such bumps as I am encountering here.

Thamks in advance


Myle

 

[Peter T]

Not sure I follow the problem, are you saying it returns a wrong value, or
the way you see it it ought to return a wrong value but strangely returns
the correct value!

This should show the process (passes a range and offset along the lines I
mentioned last time)


Sub Combinations2()
Dim n As Integer, m As Integer
'numcomb = 0
'n = InputBox("Number of items?", , 10)
'm = InputBox("Taken how many at a time?", , 3)
n = 9
m = 3
Worksheets(1).Cells.Clear
com2 n, m, 1, "'", Worksheets(1).Range("A1"), 0

End Sub

'Generate combinations of integers k..n taken m at c time, recursively
Sub com2(ByVal n%, ByVal m%, ByVal k%, ByVal s As String, _
ByRef cel As Range, ByRef nOffset As Long, _
Optional ByVal c As Long, _
Optional ByRef rDebug As Range, Optional ByRef d As Long)
Static a As Long

If c = 0 Then
a = 0
With cel.Parent
Set rDebug = .Range(.Cells(1, 3), .Cells(1, 12))
End With

rDebug.Value = Array("In", "exit1", "exit2", _
"Recurse1", "Recurse2", "exit3", _
"n", "m", "k", "s", "address")
d = 1
End If

a = a + 1 ' static: proc no.
c = c + 1 ' passed byVal: proc level
d = d + 1 ' passed byRef: debug print offset

rDebug.Rows(d).Value = Array(a & "in-" & n, "", "", _
"", "", "", _
n, m, k, s)

If m > n - k + 1 Then
d = d + 1
rDebug(d, 2) = a & "ex1-" & c
Exit Sub
End If

If m = 0 Then
cel.Offset(nOffset, 0) = s

d = d + 1
rDebug(d, 10) = s
rDebug(d, 11) = cel.Offset(nOffset, 0).Address(0, 0)
nOffset = nOffset + 1

rDebug(d, 3) = a & "ex2-" & c
Exit Sub
End If

d = d + 1
rDebug(d, 4) = a & "rec1-" & c
com2 n, m - 1, k + 1, s & k & " ", cel, nOffset, c, rDebug, d

d = d + 1
rDebug(d, 5) = a & "rec2-" & c
com2 n, m, k + 1, s, cel, nOffset, c, rDebug, d

d = d + 1
rDebug(d, 6) = a & "ex3-" & c & " "

End Sub

Regards,
Peter T