用递归计算股权层级

一、问题背景：

一个集团公司下设有多层企业，整体的股权结构呈垂直特征，即A公司控制B公司、B公司控制C公司，依次向下，现在想获取每个公司在这个垂直结构中的股权层级，如果是顶层的A公司，就是1级，层级越低，级数越大，这里约定：假如一个公司G即被母公司A直接持股，也被A公司的子公司B公司直接持股，则G的层级取2，而非3。案例测试数据为：

一个简单的股权结构

形象的说，就是对于每个子公司，找到最短的“回A之路”。你可以先不看下面的代码，想一想应该怎么解决这个问题。

二、代码实现如下：

a=Ctrsht['子公司'].unique().tolist()#数组a记录了去除所有的非重复机构
b=[]#数组b用于记录每个机构的层级
def levelsearch(level,name):
    if name=='A':#递归函数必须由明确的退出机制，否则就是死循环
        return(level,name)#当传入的机构名称为A时，表示子公司顺着股权路径找到了A公司，这时level就是返回的级数
    else:#如果尚未返回A公司，则记录此时寻找到的母公司是哪一个
        for i in range(len(Ctrsht['子公司'])):#遍历上面的dataframe
            if Ctrsht.iloc[i,1]==name:#定位当前传入的机构名称的所在行
                if Ctrsht.iloc[i,0]=='A':#如果该行的母公司即为A则返回层数
                    return(level+1,'A')
                else:
                    return(levelsearch(level+1,Ctrsht.iloc[i,0]))#如果该行的母公司不是A，则调用函数本身，下一次传入的机构名称即该行的母公司
            else:
                pass
for i in range(len(a)):#遍历子公司数组，计算每个子公司的层级
    b.append(levelsearch(1,a[i])[0])
equitylevel=pd.DataFrame(a)
equitylevel['股权层级']=b
equitylevel

股权层级

三、改进：

上述程序有个问题：有的子公司出现了多次，比如F公司，程序返回层级为F第一次出现时的股权层级，即为3（A--B--F），而如果源数据文件中将第6行E->F放在B->F前面，则程序返回的F层级就是6（A--B--C--D--E--F）。
因此当前的结果依赖于股权结构表的排序，需要进一步完善。

完善步骤为：
1、找到某公司在“子公司”列中出现的所有行数（F公司就是第5行和第6行）
2、分别计算该公司在各行时返回的股权层级（F公司就是3和4）
3、根据问题的初始规定原则，取过程2中的最小值

这里有个一非常绕的情境，就是F的母公司E，在各行也出现了两次，两种回A的路径分别是ABCDE和ABCE，这样返回的F股权层级就是6和5，按照规定原则，结果应该是5（即选择ABCE路径），所以在递归函数的定义中，必须用循环将最佳回A路径找出。

首先定义递归函数

#2020/3/7改进
#3/7改进2
def levelsearch(level,position,name):#level为初始层级，一般为1，position为子公司所在行数
    if name=='A':#name记录当前子公司的母公司，如果为A则跳出递归程序
        return(level,position,name)
    else:
        if Ctrsht.iloc[position,1]==name:
            if Ctrsht.iloc[position,0]=='A':#如果当前子公司的母公司为A，则层级加1，递归结束
                return(level+1,position,'A')
            else:#如果当前子公司的母公司不为A，先记录母公司在“子公司”列出现的行数，然后调用程序自身
                temPosition=[]
                for i in range(len(Ctrsht['子公司'])):
                    if Ctrsht.iloc[i,1]==Ctrsht.iloc[position,0]:
                        temPosition.append(i)#母公司在“子公司”列出现的行数可能为多个，必须用数组记录，并遍历数组调用递归函数
                templevel={}#用字典记录母公司每次返回的股权层级
                levelsig=0
                for k in temPosition:
                    templevel[k]=levelsearch(levelsig,k,Ctrsht.iloc[k,1])[0]
                minilevel = min(templevel, key=lambda x:templevel[x])
                return(levelsearch(level+1,minilevel,Ctrsht.iloc[minilevel,1]))
        else:
            pass

然后对每个子公司分别计算出现的行数，并调用递归函数计算min{基于各行数计算的股权层级}

a=Ctrsht['子公司'].unique().tolist()#去除所有的非重复机构
b=[]#记录每个机构的层级
for i in range(len(a)):
    linenum=[]#获得每个机构在持股机构列中出现的行数
    for k in range(len(Ctrsht['子公司'])):
        if Ctrsht.iloc[k,1]==a[i]:
            linenum.append(k)
    agencylevel=[]#记录不同出现行数计算的股权层级
    for j in linenum:
        agencylevel.append(levelsearch(1,j,a[i])[0])
    b.append(min(agencylevel))
equitylevel=pd.DataFrame(a)
equitylevel['改进的股权层级']=b
equitylevel

image.png

可以看到E的股权层级得到了修正。
下面这个图可以看到，F的层级是在比较3和5之后，选择的最小值，E的层级是在比较4和5之后，选择的最小值

结语：递归是目前我写过最难的程序了，对逻辑的要求高，中间的各种计数变量、临时变量也多，大脑要清醒，但递归代码的简洁和高效也使递归成为应用非常广泛的算法
算是刚入了门，以后再修炼吧~

用递归计算股权层级