-
1 Attachment(s)
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%.
-
Re: Recursive logic problem
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?
-
Re: Recursive logic problem
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.
-
Re: Recursive logic problem
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
-
Re: Recursive logic problem
You can't do recursive queries in Access, but if you were using SQL Server, I could have done it for you.
-
Re: Recursive logic problem
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?
-
Re: Recursive logic problem
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)?
-
Re: Recursive logic problem
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.
-
Re: Recursive logic problem
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.
-
Re: Recursive logic problem
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 ...
- Is it really "recursive" or is it perhaps just "nested" If. End Ifs?
- Is the branch diagram always the same (per your image), or could it vary?
Spoo
-
Re: Recursive logic problem
Quote:
Originally Posted by
Spoo
AZD
OK.
I guess all I have at this point is a few questions ...
- Is it really "recursive" or is it perhaps just "nested" If. End Ifs?
- 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%).
-
Re: Recursive logic problem
I think you're confusing "iterative" for "recursive." Are you required to use a recursive algorithm to solve this problem?
-
Re: Recursive logic problem
Not required to use any type of logic, just as long as it gets done :)
-
Re: Recursive logic problem
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?
-
Re: Recursive logic problem
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 ...
- assume that it is 100 (ie, "overkill")
- Dim an array with 100 elements
- At each "split", record the current percent
- 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
-
Re: Recursive logic problem
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 ...
- assume that it is 100 (ie, "overkill")
- Dim an array with 100 elements
- At each "split", record the current percent
- 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.
-
Re: Recursive logic problem
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.
-
Re: Recursive logic problem
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
-
Re: Recursive logic problem
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.
-
1 Attachment(s)
Re: Recursive logic problem
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]
-
Re: Recursive logic problem
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...
-
Re: Recursive logic problem
Unfortunatelly MySQL does not support CTE (Recursive SQL)
-
Re: Recursive logic problem
MySQL doesn't have the WITH command. What does that do, maybe there's an equivalent?
-
Re: Recursive logic problem
Well then I re-curse at MySQL lol
-
Re: Recursive logic problem
In you original post, given "A-B-75%", is "A" the Base or the Split?
-
Re: Recursive logic problem
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.
-
Re: Recursive logic problem
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?
-
Re: Recursive logic problem
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
-
Re: Recursive logic problem
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.
-
Re: Recursive logic problem
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
-
Re: Recursive logic problem
Are elements of the [Split] column of [YRR Revenue Split] unique? If not, you've got a much bigger can of worms.
-
Re: Recursive logic problem
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)
-
Re: Recursive logic problem
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.
-
Re: Recursive logic problem
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
-
Re: Recursive logic problem
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)?
-
Re: Recursive logic problem
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?
-
Re: Recursive logic problem
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.
-
Re: Recursive logic problem
This helps. Now then, is the unique account in the commissions table a Master or a Split?
-
Re: Recursive logic problem
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.
-
Re: Recursive logic problem
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)?
-
Re: Recursive logic problem
-
Re: Recursive logic problem
So you are in fact calling GetPercent(A) (thus contradicting your answer in post #28)
-
Re: Recursive logic problem
It's quite possible I've contradicted myself lol.
-
Re: Recursive logic problem
I think you should take a step back, and re-think how to make this simple and re-write your first question in a way that makes sense to us.
Give more example results, etc.
For example write code that creates a list of some of your values, so we can test on our own machines.
PS. Are the values in my post #20 correct? If yes, then why not try to replicate the logic in VB?
Also. I agree with jcis that you should put your data into an array, and then work with it (if you are to do it in VB)
-
Re: Recursive logic problem
This is why I am so confused. Referring again to the image in your original post, your function Revenues() from post #30, which calls GetPercent(), seems like it wants to iterate through the leaf elements of the tree (C, E, F, H, K, L, & M). In other words, GetPercent() traverses UP the tree.
However, you are also implying the the Commissions table would contain A, and not (C, E, F, H, K, L & M).
Thus, it seems like Revenue is calling GetPercent(A), and GetPercent() traverses up. However, since A is already a root node, it only climbs up one level and exits, thus giving you no useful functionality.
-
Re: Recursive logic problem
Ya, I'm rewriting it now. I think I'm close. I'll come back if I need your help again.
Thanks, guys!
-
Re: Recursive logic problem
when i was a boy we built the trees and simply rolled coins down then returning the value as we went
the tree can be traversed in any number of ways
the norm is right node left an in-order traversal for a l<n>r structure
in essence you walk the tree to the left untill you find a nul pointer at the leftchild and insert the sum of ther colected value at the current node then step back to the current node and walk as far right as you can putting the value in the current node when the right child is null
when the walk is complete the values are in the appropriate nodes
here to help more if needed
