Recursive logic problem

Hey,

I've been working on this for hours and am no closer to a solution. I need help creating a recursive function. I've upload an image to help you visualize the problem.

I have a table of records (the bottom part of the image) that determines which splits occur and what percentage goes to each "account". The first column is the Master, the second is what it splits into, and the third is what percentage the split has.

All that matters to me is when an account can't be split anymore. I've circled them in red for clarity. What I need is something that will tell me what the bottom percentages are.

For example, A splits into B at 75% and B splits into C at 50%. That means C gets 50% of 75% which is 37.5%.

Quote:

---

Originally Posted by AZDJedi

I have a table of records (the bottom part of the image) that determines which splits occur and what percentage goes to each "account". The first column is the Master, the second is what it splits into, and the third is what percentage the split has.

---

So this means you data is in a database ?

Maybe it is easier to do this on the database level (as a query)? what database do you use? and what is your table format?

Quote:

---

Originally Posted by CVMichael

So this means you data is in a database ?

Maybe it is easier to do this on the database level (as a query)? what database do you use? and what is your table format?

---

Yes, it's in MS Access. I can't do it as a query with my skills. I'm not sure it's even possible to do a recursive SQL query. Either way - as VB code or SQL queries - I still need to get the logic right.

AZD

You have "manually" solved the algo for C per ...

Quote:

---

For example, A splits into B at 75% and B splits into C at 50%.
That means C gets 50% of 75% which is 37.5%.

---

... so, what is it that you "need"?

Perhaps you could post a snippet of your code (preferably using
the "Code" wrapper as opposed to an attachment)

Spoo

You can't do recursive queries in Access, but if you were using SQL Server, I could have done it for you.

Quote:

---

Originally Posted by CVMichael

You can't do recursive queries in Access, but if you were using SQL Server, I could have done it for you.

---

Technically I'm using MySQL. Can you do it in that?

What have you written so far? Specifically, have you already read in the data and are storing it in an array or some other data structure? If so, how is that data accessed? CVMichael correctly points out that this is very easy to do if the data is already in a queryable database. If it is not in a database (and you don't want to deal with the overhead of putting it in a database), then the algorithm that best suits the problem depends on the data structures you are using.

Edit: You posted an answer to my question while I typed.

Can you post the structure of the table containing this data (aka the column names and such)?

Quote:

---

Originally Posted by Spoo

AZD

You have "manually" solved the algo for C per ...

... so, what is it that you "need"?

Perhaps you could post a snippet of your code (preferably using
the "Code" wrapper as opposed to an attachment)

Spoo

---

Spoo, I'm not sure what else you need from me. I only have incomplete code but the logic isn't right, it only goes one step down for each lower level then it stops.

Quote:

---

Originally Posted by Lenggries

What have you written so far? Specifically, have you already read in the data and are storing it in an array or some other data structure? If so, how is that data accessed? CVMichael correctly points out that this is very easy to do if the data is already in a queryable database. If it is not in a database (and you don't want to deal with the overhead of putting it in a database), then the algorithm that best suits the problem depends on the data structures you are using.

---

The data sits on a MySQL server which I connect to via MS Access. I can query it fine; I have complete access to the array (table) of information I just can't figure out the logic to get to the bottom of the tree consistently.

Quote:

---

Originally Posted by AZDJedi

Spoo, I'm not sure what else you need from me. I only have incomplete code but the logic isn't right, it only goes one step down for each lower level then it stops.

---

AZD

OK.
I guess all I have at this point is a few questions ...

1. Is it really "recursive" or is it perhaps just "nested" If. End Ifs?
2. Is the branch diagram always the same (per your image), or could it vary?

Spoo

Quote:

---

Originally Posted by Spoo

AZD

OK.
I guess all I have at this point is a few questions ...

1. Is it really "recursive" or is it perhaps just "nested" If. End Ifs?
2. Is the branch diagram always the same (per your image), or could it vary?

Spoo

---

The image is just an example. It will vary. It's definitely recursive because A could be split all the way down to Z, in theory. The only IF that I need is checking if the code gets split further (either because an EOF is encountered or the Percentage is 100%).

I think you're confusing "iterative" for "recursive." Are you required to use a recursive algorithm to solve this problem?

Not required to use any type of logic, just as long as it gets done :)

OK, given the input in your original post, what do you want the output to be, and should the output be printed ot a screen, a file, or saved in teh DB?

Quote:

---

Originally Posted by AZDJedi

The image is just an example. It will vary. It's definitely recursive because A could be split all the way down to Z, in theory. The only IF that I need is checking if the code gets split further (either because an EOF is encountered or the Percentage is 100%).

---

AZD

OK, that helps.

The question then becomes .. what is the maximum number of
"indents" (ie, number of "splits") that can occur?

If this is unknown, perhaps a "brute" force approach would be ...

1. assume that it is 100 (ie, "overkill")
2. Dim an array with 100 elements
3. At each "split", record the current percent
4. When the end has been reached, just multiply all "filled" element
   percentages to get the "final" percentage.

Hope that gives you a starting point.

Spoo

Quote:

---

Originally Posted by Spoo

AZD

OK, that helps.

The question then becomes .. what is the maximum number of
"indents" (ie, number of "splits") that can occur?

If this is unknown, perhaps a "brute" force approach would be ...

1. assume that it is 100 (ie, "overkill")
2. Dim an array with 100 elements
3. At each "split", record the current percent
4. When the end has been reached, just multiply all "filled" element
   percentages to get the "final" percentage.

Hope that gives you a starting point.

Spoo

---

Spoo,

That's the approach I took. In theory it could be split infinite times. In practise, probably a max of 2-4.

I don't need an array, because I just have to know what the current one is, which I then save to a temporary table for that Account. I then go to the next Account and find it's final percentage.

Code:

---

Private Function GetPercent(strBase As String, sngPercent As Single) As Single
    Dim rs As New ADODB.Recordset
   
    rs.Open "SELECT * FROM [YRR Revenue Split] WHERE Split='" & strBase & "'", CurrentProject.Connection, adOpenForwardOnly
        If rs.EOF = False Then
            If rs!SplitPercent <> 1 Then
                GetPercent = GetPercent(rs!Base, sngPercent * rs!SplitPercent)
            Else
                GetPercent = sngPercent
                strLatestSplit = strBase
            End If
        Else
            GetPercent = sngPercent
            strLatestSplit = strBase
        End If
    rs.Close
   
    Set rs = Nothing
End Function

---

That's what I'm working with. I enter the function for the first time using a loop through a recordset that has a list of all the Accounts. The current problem is it only goes one level deep.

As I recall, VB6 can be counterintuitive with checking if a recordset is empty. Try replacing your first IF statement with this:

Code:

---

If Not (rs.BOF = True And rs.EOF = True) Then

---

Quote:

---

Originally Posted by Lenggries

As I recall, VB6 can be counterintuitive with checking if a recordset is empty. Try replacing your first IF statement with this:

Code:

---

If Not (rs.BOF = True And rs.EOF = True) Then

---

---

The problem isn't there, I step through, and it works as it should. It's my underlying logic that is the problem...it doesn't take into account that A could split to B and then B could split to C and then that it needs to go BACK to A to see if it splits again to D.

Just to show you how awesome SQL Server is :D

Code:

---

DECLARE @tmp TABLE(
          ID                        INT PRIMARY KEY
        , ParentID                INT NULL
        , NodeChar                VARCHAR(100)
        , NumPercent        FLOAT
)

INSERT INTO @tmp
SELECT 1, NULL, 'A', 1.00 UNION ALL

SELECT 2,    1, 'B', 0.75 UNION ALL
SELECT 3,    1, 'G', 0.75 UNION ALL

SELECT 4,    2, 'C', 0.50 UNION ALL
SELECT 5,    2, 'D', 0.50 UNION ALL

SELECT 6,    5, 'E', 0.90 UNION ALL
SELECT 7,    5, 'F', 0.10 UNION ALL

SELECT 8,    3, 'J', 0.80 UNION ALL
SELECT 9,    3, 'H', 0.20 UNION ALL

SELECT 10,  8, 'K', 0.33 UNION ALL
SELECT 11,  8, 'L', 0.33 UNION ALL
SELECT 12,  8, 'M', 0.33


; WITH
aa AS (
        -- Get records that do not have children
        SELECT t1.*
                , t1.NumPercent AS AccumulatedPercent
                , t1.NodeChar AS AccumulatedChars
                , 1 AS [Level]
                , t1.ID AS Start_ID
        FROM @tmp AS t1
                LEFT JOIN @tmp AS t2 ON t1.ID = t2.ParentID
        WHERE t2.ID IS NULL
       
        UNION ALL
       
        -- Join with it's parent
        SELECT t1.*
                , AccumulatedPercent * t1.NumPercent
                , CAST(AccumulatedChars + ', ' + t1.NodeChar AS VARCHAR(100))
                , [Level] + 1
                , Start_ID
        FROM @tmp AS t1
                INNER JOIN aa AS t2 ON t2.ParentID = t1.ID
        --WHERE t1.ParentID IS NOT NULL -- we don't need first node 'A'
)
, bb AS (
        SELECT Start_ID, MAX([Level]) AS MAX_Level
        FROM aa
        GROUP BY Start_ID
)
SELECT aa.Start_ID
        , t.NodeChar AS [Top Node Char]
        , aa.[Level] AS [Total Levels]
        , aa.AccumulatedPercent * 100.0 AS [Accumulated Percent]
        , aa.AccumulatedChars
FROM aa
        INNER JOIN bb ON aa.Start_ID = bb.Start_ID AND aa.[Level] = bb.MAX_Level
        INNER JOIN @tmp AS t ON t.ID = aa.Start_ID
ORDER BY aa.Start_ID, aa.[Level]

---

Quote:

---

Originally Posted by CVMichael

Just to show you how awesome SQL Server is :D

Code:

---

DECLARE @tmp TABLE(
          ID                        INT PRIMARY KEY
        , ParentID                INT NULL
        , NodeChar                VARCHAR(100)
        , NumPercent        FLOAT
)

INSERT INTO @tmp
SELECT 1, NULL, 'A', 1.00 UNION ALL

SELECT 2,    1, 'B', 0.75 UNION ALL
SELECT 3,    1, 'G', 0.75 UNION ALL

SELECT 4,    2, 'C', 0.50 UNION ALL
SELECT 5,    2, 'D', 0.50 UNION ALL

SELECT 6,    5, 'E', 0.90 UNION ALL
SELECT 7,    5, 'F', 0.10 UNION ALL

SELECT 8,    3, 'J', 0.80 UNION ALL
SELECT 9,    3, 'H', 0.20 UNION ALL

SELECT 10,  8, 'K', 0.33 UNION ALL
SELECT 11,  8, 'L', 0.33 UNION ALL
SELECT 12,  8, 'M', 0.33


; WITH
aa AS (
        -- Get records that do not have children
        SELECT t1.*
                , t1.NumPercent AS AccumulatedPercent
                , t1.NodeChar AS AccumulatedChars
                , 1 AS [Level]
                , t1.ID AS Start_ID
        FROM @tmp AS t1
                LEFT JOIN @tmp AS t2 ON t1.ID = t2.ParentID
        WHERE t2.ID IS NULL
       
        UNION ALL
       
        -- Join with it's parent
        SELECT t1.*
                , AccumulatedPercent * t1.NumPercent
                , CAST(AccumulatedChars + ', ' + t1.NodeChar AS VARCHAR(100))
                , [Level] + 1
                , Start_ID
        FROM @tmp AS t1
                INNER JOIN aa AS t2 ON t2.ParentID = t1.ID
        --WHERE t1.ParentID IS NOT NULL -- we don't need first node 'A'
)
, bb AS (
        SELECT Start_ID, MAX([Level]) AS MAX_Level
        FROM aa
        GROUP BY Start_ID
)
SELECT aa.Start_ID
        , t.NodeChar AS [Top Node Char]
        , aa.[Level] AS [Total Levels]
        , aa.AccumulatedPercent * 100.0 AS [Accumulated Percent]
        , aa.AccumulatedChars
FROM aa
        INNER JOIN bb ON aa.Start_ID = bb.Start_ID AND aa.[Level] = bb.MAX_Level
        INNER JOIN @tmp AS t ON t.ID = aa.Start_ID
ORDER BY aa.Start_ID, aa.[Level]

---

---

DAMN!! I think that's it. I wonder if I can port that to MySQL...

Unfortunatelly MySQL does not support CTE (Recursive SQL)

MySQL doesn't have the WITH command. What does that do, maybe there's an equivalent?

Well then I re-curse at MySQL lol

In you original post, given "A-B-75%", is "A" the Base or the Split?

Quote:

---

Originally Posted by Lenggries

In you original post, given "A-B-75%", is "A" the Base or the Split?

---

A is the base. Keep in mind that there are many bases. I'm trying to calculate salesman commisions, and some "teams" split the commission. So I'll call my above example Salesperson A1. Salesperson A2 could have a totally different tree.

If A is the base, then I don't understand what GetPercent is supposed to return. If I call GetPercent("A",1) (not sure what to pass as the percent parameter), what should it return?

GetPercent(A) wouldn't be called.

in psuedo code:

for each Base
getpercent(rs!split,rs!Percent)

I would need that to return the bottom most percent (for a Base of A, that would be C at 37.5%)
I would then need it to go back to the top (where it splits at B) and give me D...which it would continue to recursively go into until it spit out E (at 17% or something) and then again F (at 17%)
next

The naming of variables was confusing me. Try this:

Code:

---

Private Function GetPercent(strSplit As String, Optional sngPercent As Single = 1#) As Single
    Dim rs As New ADODB.Recordset
    Dim strBase As String
    Dim sngNewPercent as Single
   
    rs.Open "SELECT * FROM [YRR Revenue Split] WHERE Split='" & strSplit & "'", CurrentProject.Connection, adOpenForwardOnly
        If Not (rs.BOF = True And rs.EOF = True) Then
            strBase = rs!Base
            sngNewPercent = rs!SplitPercent
            rs.Close
            strLatestSplit = strBase
            GetPercent = GetPercent(strBase, sngPercent * sngNewPercent)
        Else
            rs.Close
            GetPercent = sngPercent
            strLatestSplit = strSplit
        End If
    Set rs = Nothing
End Function

---

A couple points:
- The primary change is that I am closing the recordset before initiating the recursive step. That way I don't have all these recordsets sitting on the stack possibly clobbering one another.

- I made the second parameter optional. That way you don't actually have to call GetPercent("C",1), but rather you can just call GetPercent("C")

- I got rid of the inside If-Then statement because it didn't do anything useful

- I'm not used to working with mySQL, but your method of declaring rs and opening the table looks odd to me. If my function doesn't work, this might be something to look at.

- strLatestSplit is undefined. If it is a global variable, it is probably a bad one. I suggest making that another parameter of the function.

Quote:

---

Originally Posted by Lenggries

The naming of variables was confusing me. Try this:

Code:

---

Private Function GetPercent(strSplit As String, Optional sngPercent As Single = 1#) As Single
    Dim rs As New ADODB.Recordset
    Dim strBase As String
    Dim sngNewPercent as Single
   
    rs.Open "SELECT * FROM [YRR Revenue Split] WHERE Split='" & strSplit & "'", CurrentProject.Connection, adOpenForwardOnly
        If Not (rs.BOF = True And rs.EOF = True) Then
            strBase = rs!Base
            sngNewPercent = rs!SplitPercent
            rs.Close
            strLatestSplit = strBase
            GetPercent = GetPercent(strBase, sngPercent * sngNewPercent)
        Else
            rs.Close
            GetPercent = sngPercent
            strLatestSplit = strSplit
        End If
    Set rs = Nothing
End Function

---

A couple points:
- The primary change is that I am closing the recordset before initiating the recursive step. That way I don't have all these recordsets sitting on the stack possibly clobbering one another.

- I made the second parameter optional. That way you don't actually have to call GetPercent("C",1), but rather you can just call GetPercent("C")

- I got rid of the inside If-Then statement because it didn't do anything useful

- I'm not used to working with mySQL, but your method of declaring rs and opening the table looks odd to me. If my function doesn't work, this might be something to look at.

- strLatestSplit is undefined. If it is a global variable, it is probably a bad one. I suggest making that another parameter of the function.

---

Thanks, I think you're on to something. Here is the parent function. It goes one level deep and then skips to the next Account.

Code:

---

Sub Revenues(DateFrom As Date, DateTo As Date, Optional sYRR As String)
    'call revenues(#10/1/2011#,#10/31/2011#)
    Dim rsYRR As New ADODB.Recordset
    Dim rsSub As New ADODB.Recordset
    Dim rsSub2 As New ADODB.Recordset
   
    Dim sngPercent As Single
    Dim strSplit As String
    Dim curCommission As Currency
   
   
    'Loop through each YRR
    rsYRR.Open ("[TEMP Commission]"), CurrentProject.Connection, adOpenForwardOnly, adLockOptimistic
    Do Until rsYRR.EOF
        sngPercent = 1
        curCommission = Nz(DSum("Commission", "YRR Commissions Query", "YRR='" & rsYRR!YRR & "' AND statement_date BETWEEN #" & DateFrom & "# AND #" & DateTo & "#")) 'This gets the Base Accounts commissions
       
curCommission = 100 'Just for testing
       
        If curCommission <> 0 Then
            rsYRR!Gross = Nz(rsYRR!Gross) + curCommission
            rsYRR.Update
            strLatestSplit = ""
           
            'Loop through the Split (thus looping through each Base)
            rsSub.Open ("SELECT * FROM [YRR Revenue Split] WHERE Split='" & rsYRR!YRR & "'"), CurrentProject.Connection, adOpenForwardOnly
                Do
                    sngPercent = GetPercent(rsSub!Base, rsSub!SplitPercent)
                   
                    DoCmd.RunSQL ("UPDATE [TEMP Commission] SET Net=Nz(Net)+" & curCommission * sngPercent & " WHERE YRR='" & strLatestSplit & "'")
                   
                    rsSub.MoveNext
                Loop Until rsSub.EOF
            rsSub.Close
        End If
       
        rsYRR.MoveNext
    Loop
   
    rsYRR.Close
   
    Set rsYRR = Nothing
    Set rsSub = Nothing
    Set rsSub2 = Nothing
End Sub

---

Somewhere I need another nested loop so I don't lose each of the child iterations

Are elements of the [Split] column of [YRR Revenue Split] unique? If not, you've got a much bigger can of worms.

Quote:

---

Originally Posted by Lenggries

Are elements of the [Split] column of [YRR Revenue Split] unique? If not, you've got a much bigger can of worms.

---

No, because there needs to be a link to more than one child.

A-B
B-C (end node)
B-D
D-E (end node)
D-F (end node)

Quote:

---

Originally Posted by AZDJedi

No, because there needs to be a link to more than one child.

A-B
B-C (end node)
B-D
D-E (end node)
D-F (end node)

---

I though [Split] was the second column. Those items are unique in your example.

I know, the naming convention is bogus...I have no choice in it; I would have changed it in my code to Master,Split but that would confuse me when dealing with Split,Base from the table.

Columns are:

ID, INT AUTO
Split, CHAR(3)
Base, CHAR(3)
SplitPercent SINGLE

For some accounts there are no splits so the record is just AAA,AAA,100, but a majority of them are as above

Yes, the naming conventions are very confusing. Your recent post doesn't square with your answer in post #26:

Quote:

---

Originally Posted by AZDJedi

Quote:

---

Originally Posted by Lenggries

In you original post, given "A-B-75%", is "A" the Base or the Split?

---

A is the base.

---

That said, are the elements in the BASE column unique (or distinct, if you prefer)?

Let's start over. Let's call them Master and Split for our conversation.

There is no uniqueness in any column. (Master+Split will be unique because A can't split into B with more than one percentage.)

1) Get a list of all accounts that have commissions this month
2) Iterate through that unique list
-- a) recurse through each record found in the "Master-Split" table
---- b) Recurse through each record for any Splits that point back to a Master record until it reaches the last node.
------ c) Go back to A for the next Master record


Make sense or did I confuse it more?

It is true that it is a good practice moving your code to back end, we use to say here: "hey, better make a direct SQL query to your table" or "Use a stored procedure in MSSQL Server" or "use a view in Access", BUT: In cases like this it's exactly the opposite: When you need to handle complex calculations/Functions/Recursive calls VB is much better just because it is more flexible. In short, i think you'll make your life easier if you just read all the data in the table/s into an array/collection/whatever into VB and then let VB make the magic. Just my opinion.

This helps. Now then, is the unique account in the commissions table a Master or a Split?

Quote:

---

Originally Posted by Lenggries

This helps. Now then, is the unique account in the commissions table a Master or a Split?

---

The Commission loop will only look at Master...but Account A could be in both Master and Split since A could split to B and C, and Master D could split to A and E, for example - which means it would then subsplit into B and C.

I'm sorry, but I'm confused again. Referring to the image in your original post, is A a master (and thus also an account in the commissions table)?