+ Reply to Thread
Results 1 to 4 of 4

Recursive Code

  1. #1
    Forum Contributor
    Join Date
    11-11-2005
    Posts
    267

    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

  2. #2
    Peter T
    Guest

    Re: Recursive Code

    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
    >




  3. #3
    Forum Contributor
    Join Date
    11-11-2005
    Posts
    267
    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

  4. #4
    Peter T
    Guest

    Re: Recursive Code

    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
    >




+ Reply to Thread

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts

Search Engine Friendly URLs by vBSEO 3.6.0 RC 1