Recursive Code

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

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" <[email protected]> wrote in
message news:[email protected]...
>
> 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
>
>
> --
> Myles
> ------------------------------------------------------------------------
> Myles's Profile:
http://www.excelforum.com/member.php...o&userid=28746
> View this thread: http://www.excelforum.com/showthread...hreadid=571143
>

Many thanks Peter for your incisive response.

Given that recursive codes "recoil" upon themselves, ever looking 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 the diminishing vales of m till m=0. At this point in time, one set (of 3 values) -using my example of 3 Combin 9-will have been amassed and 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 stanza embedded in its bowel, another cycle is commisioned. The puzzle is that while the first pass yields the combination set 1 2 3, the second delivers 1 2 4 (the third 1 2 5 and so on). Assuming that the 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 " " . This scenario should reproduce the same result 1 2 3 as before. I am at loss 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 and results logical. No such bumps as I am encountering here.

Thamks in advance


Myles

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

"Myles" <[email protected]> wrote in
message news:[email protected]...
>
> Many thanks Peter for your incisive response.
>
> Given that recursive codes "recoil" upon themselves, ever looking
> 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 the
> diminishing vales of m till m=0. At this point in time, one set (of 3
> values) -using my example of 3 Combin 9-will have been amassed and
> 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 stanza
> embedded in its bowel, another cycle is commisioned. The puzzle is that
> while the first pass yields the combination set 1 2 3, the second
> delivers 1 2 4 (the third 1 2 5 and so on). Assuming that the
> 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 " " . This
> scenario should reproduce the same result 1 2 3 as before. I am at loss
> 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 and
> results logical. No such bumps as I am encountering here.
>
> Thamks in advance
>
>
> Myles
>
>
> --
> Myles
> ------------------------------------------------------------------------
> Myles's Profile:
http://www.excelforum.com/member.php...o&userid=28746
> View this thread: http://www.excelforum.com/showthread...hreadid=571143
>