浅谈递归在BOM上的应用

roych

前几天有版友发帖《求个查询，见附件。Bom 成本》，我当时回复了句，分解到底层就好了。不过那几天比较忙就没有继续写例子了。一般来说，对于树形结构的问题，都是层层钻取，直达底层最后得出结果的。至于这过程中，使用递归算法还是使用循环算法，则看个人喜好了。通常情况下，递归能解决的问题，循环一样没问题的。只不过有些版友可能对递归算法不太熟悉，常常会造成一些困惑罢了。
递归其实并不算太难，论坛上也有一些经典写法。例如，斐波纳契（Fibonacci）数列和树形菜单。

我们现在回头来看看这个例子。假定某个成品需要1个001，那么拆解下来，最终需要几个基础部件呢？按我的理解是，一个001=1个002+2个003，1个002=1个004+1个009,1个003=2个004+1个005，相当于5个004+2个005+1个009…如此类推，最终无法分解之后则是我们想要的结果。拆解过程如图所示：

按惯例，还是先上传代码和附件。

1. Function getParent(ByVal dicParent As Dictionary) As Dictionary
   
2.     Dim rst As New ADODB.Recordset
   
3.     Dim dict As New Dictionary
   
4.     Dim dict1 As New Dictionary
   
5.     Dim strParent As String
   
6.     Dim strWh As String
   
7.     Dim strSQL As String
   
8.     Dim i As Long
   
9.     Dim j As Long
   
10.    
    
11.     For i = 0 To dicParent.Count - 1
    
12.         strParent = dicParent.Keys(i)
    
13.         strSQL = "select "
    
14.         strSQL = strSQL & " 子编码,用量 from Bom明细表 where 父编码='" & strParent & "'"
    
15.         rst.Open strSQL, CurrentProject.Connection, adOpenKeyset, adLockOptimistic
    
16.         '如果存在下级
    
17.         If rst.RecordCount > 0 Then
    
18.             Do Until rst.EOF
    
19.                 If dict1.Exists(rst(0).Value) Then
    
20.                 '如果已经存在键值，则将合计。例子里BOM有互相交叉的情况，因此加上这句。
    
21.                 '例如，002和003分属001，按一般原则，接下来应该是两条无交集的支线，而例子里002和003都含有004
    
22.                     dict1.Item(rst(0).Value) = dict1.Item(rst(0).Value) + rst(1).Value * dicParent.Items(i)
    
23.                 Else
    
24.                 '如果不存在键值，表示得到新物料。
    
25.                     dict1.Add rst(0).Value, rst(1).Value * dicParent.Items(i)
    
26.                 End If
    
27.                 rst.MoveNext
    
28.             Loop
    
29.         Else
    
30.         '如果不存在新的下级物料，则进行合计
    
31.             dict1.Item(strParent) = dict1.Item(strParent) + dicParent.Items(i)
    
32.         End If
    
33.         rst.Close
    
34.     Next
    
35. '拼接条件子句，备用
    
36.     Set dict = dict1
    
37.     For i = 0 To dict.Count - 1
    
38.         strWh = strWh & "父编码='" & dict.Keys(i) & "' or "
    
39.     Next
    
40. 
    
41.     strSQL = "select"
    
42.     strSQL = strSQL & " count(*) from Bom明细表 where " & Left(strWh, Len(strWh) - 4)
    
43.     rst.Open strSQL, CurrentProject.Connection, adOpenKeyset, adLockOptimistic
    
44.      '如果找到记录，表示至少还有一个没到最底层的部件，执行递归
    
45.     If rst(0) > 0 Then
    
46.         Set getParent = getParent(dict1)
    
47.     Else
    
48.     '如果找不到，则表示已到最底层，无法再分解。直接赋值即可。
    
49.         Set getParent = dict
    
50.     End If
    
51.     rst.Close
    
52. End Function

复制代码

执行的结果如下：

附件如下：

roych

有兴趣的可以继续看我当时的编写思路：

这个例子有什么不同？我们可以看到，斐波纳契数列只返回一个值；树节点则返回不参与数学计算的组件。一旦参与计算呢？这就涉及到我的知识盲区了。

我们知道，VBA和其它语言最大的一个区别就是，没法直接返回多个值。例如，Python也好，JavaScript也好，直接一句return a，arr。后面调用时，则 x，arrX = 函数(参数)，则x自动对应a，arrX对应arr。那是相当方便。VBA怎么办？——用数组把它们合成一个数组，后面再对数组解套；要么合并成字符串，再拆分。不管哪个方式，都没有其他语言方便。还有别的办法吗？有！

我们继续来观察，前面不管怎么计算，最终都是一个物料对应一个数量。这是什么？键值对。想起了什么？字典？对！接下来，考虑如何确定参数类型。理论上，参数类型并没什么限制。例如，我们可以用部件代码传入。这时候是一个字符串。传入当然没问题。但后面呢？我们使用递归时，函数返回的可是一个字典哦。再把字典改成字符串？这波操作显然相当反人类反社会。因此，我们应该传入一个字典。这样才比较符合Roych骚气十足的气质嘛。

【注：由于避免敏感字，这里的“select”加了空格，完整代码请参考1楼。顺带圈一下站长@admin ，每次发帖都这么麻烦。以后对于SQL语句的回帖都发附件吗？还有就是SQL Server版块，要是去掉了SQL脚本，几乎没剩下啥了吧？】
回到For这部分，我们先传入一个字典。把键作为父编码的条件，保留值备用。这时候打开记录集，把子编码和用量添加到一个字典里，显然可以得到下一层的字典。
当字典一层层替换时，查到后面必然会间歇性出现一些无法再分解的物料号，因此这里就需要用recordcount进行判断。出现这种情况就不要替换了（否则会丢失数据），而是把已有的物料保持不变。这就是外层Else的意思。

1. For i = 0 To dicParent.Count - 1
   
2.         strParent = dicParent.Keys(i)
   
3.         strSQL = "s elect 子编码,用量 from Bom明细表 where 父编码='" & strParent & "'"
   
4.         rst.Open strSQL, CurrentProject.Connection, adOpenKeyset, adLockOptimistic
   
5.         '如果存在下级
   
6.         If rst.RecordCount > 0 Then
   
7.             Do Until rst.EOF
   
8.                 If dict1.Exists(rst(0).Value) Then
   
9.                 '如果已经存在键值，则将合计。例子里BOM有互相交叉的情况，因此加上这句。
   
10.                 '例如，002和003分属001，按一般原则，接下来应该是两条无交集的支线，而例子里002和003都含有004
    
11.                     dict1.Item(rst(0).Value) = dict1.Item(rst(0).Value) + rst(1).Value * dicParent.Items(i)
    
12.                 Else
    
13.                 '如果不存在键值，表示得到新物料。
    
14.                     dict1.Add rst(0).Value, rst(1).Value * dicParent.Items(i)
    
15.                 End If
    
16.                 rst.MoveNext
    
17.             Loop
    
18.         Else
    
19.         '如果不存在新的下级物料，则进行合计
    
20.             dict1.Item(strParent) = dict1.Item(strParent) + dicParent.Items(i)
    
21.             
    
22.         End If
    
23.         rst.Close
    
24.     Next

复制代码

讲完外层，再说内层。由于这个例子的特殊性在于各个物料号存在交叉的情况。因此，不能一步到位用Add方法进行添加。所以，查到第一个物料号时，必须看看之前是否已经存在这个物料号。例如，查完“002”下一层级时候，就必须看看“003”下一层级的物料号是否和它有重复，如果有重复，则直接把用量加上，如果不重复，则新增“003”的下一层级物料号和数量。
当这些工作做完之后，我们还需要进行一个判断，看看是否都达到了底层（即不可分解），如果达到了则返回数据，如果没达到，则递归。那么怎么判断是否达到底层呢？如果每个物料号都在父级上查不到不就可以了么？因此，接下来有这一段：

1.     Set dict = dict1
   
2.     For i = 0 To dict.Count - 1
   
3.         strWh = strWh & "父编码='" & dict.Keys(i) & "' or "
   
4.     Next
   
5. 
   
6.     strSQL = "s elect count(*) from Bom明细表 where " & Left(strWh, Len(strWh) - 4)
   
7.     rst.Open strSQL, CurrentProject.Connection, adOpenKeyset, adLockOptimistic
   
8.      '如果找到记录，表示至少还有一个没到最底层的部件，执行递归
   
9.     If rst(0) > 0 Then
   
10.         Set getParent = getParent(dict1)
    
11.     Else
    
12.     '如果找不到，则表示已到最底层，无法再分解。直接赋值即可。
    
13.         Set getParent = dict
    
14.     End If
    
15.     rst.Close

复制代码

至此整个思路已经讲解完毕，希望有助于大家理解。这个写法似乎有些繁琐，理论上应该可以进一步优化，不过这段时间怕是我没时间处理。

zhafs

学习学习！！！！谢谢！！