【摘要】
    递归运算是指直接或者间接地调用自身的运算方法。比如我们熟悉的汉诺塔问题，就是典型的递归运算。SQL 和 SPL 是大家比较熟悉的程序语言，本文将探讨对于递归问题，这两种语言的解决方案和基本原理。如何简便快捷的处理递归运算，这里为你全程解析，并提供 SQL 和 SPL 示例代码。SQL 和 SPL 的递归对比

 

一． 递归查找所有引用

 

【例 1】 下面是某公司组织结构表，查询各部门的级别（总部是 1 级，分公司 2 级，依此类推）。

ID	ORG_NAME	PARENT_ID
1	Head Office	0
2	Beijing   Branch Office	1
3	Shanghai   Branch Office	1
4	Chengdu   Branch Office	1
5	Beijing   R&D Center	2
…	…	…

 

SQL的解决方案：

    这个问题需要循环每条记录，递归查找每个机构的所有上级部门。从正常的逻辑来说，我们希望的递归是每条机构记录，都可以通过父机构 ID 找到对应的父记录，以及父记录的父记录，依此类推。但是在 SQL 中，并没有显式的记录、引用这些概念，所以我们只能递归找到有上下级关系的记录，按顺序排列，如下图所示：

 

 

在 SQL 中我们可以使用 WITH 语句进行递归查询，语句如下：

 

WITH CTE1 (ID,ORG_NAME,PARENT_ID,O_ID,O_ORG_NAME) AS(

   SELECT

      ID,ORG_NAME,PARENT_ID,ID O_ID,ORG_NAME O_ORG_NAME

   FROM ORGANIZATION

   UNION ALL

   SELECT

      ORG.ID,ORG.ORG_NAME,ORG.PARENT_ID,CTE1.O_ID,CTE1.O_ORG_NAME

   FROM ORGANIZATION ORG

   INNER JOIN CTE1

   ON ORG.ID=CTE1.PARENT_ID

)

SELECT

   O_ID ID,MIN(O_ORG_NAME) ORG_NAME,COUNT(*) "LEVEL"

FROM (

   SELECT

      ID,ORG_NAME,PARENT_ID,O_ID,O_ORG_NAME

   FROM(

      SELECT *

      FROM CTE1

      ORDER BY O_ID,ID

   )

)

GROUP BY O_ID

ORDER BY ID

 

在 ORACLE 中，我们还可以使用 START WITH … CONNECT BY … PRIOR … 进行递归查询，语句如下：

 

SELECT

   MAX(ID) ID, MAX(ORG_NAME) ORG_NAME, COUNT(*) "LEVEL"

FROM (

   SELECT

      ID,ORG_NAME,SUM(ID) OVER (ORDER BY RN) GROUP_ID

   FROM (

      SELECT

         CASE WHEN LAG(PARENT_ID,1) OVER(ORDER BY RN ASC)=0

         OR LAG(PARENT_ID,1) OVER(ORDER BY RN ASC) IS NULL THEN ID

         ELSE NULL END ID,

         CASE WHEN LAG(PARENT_ID,1) OVER(ORDER BY RN ASC)=0

         OR LAG(PARENT_ID,1) OVER(ORDER BY RN ASC) IS NULL THEN ORG_NAME

         ELSE NULL END ORG_NAME,

         RN

      FROM (

         SELECT

            ID,ORG_NAME,PARENT_ID,ROWNUM RN

         FROM ORGANIZATION ORG

         START WITH ORG.PARENT_ID>=0

         CONNECT BY ORG.ID=PRIOR ORG.PARENT_ID

      )

   )

)

GROUP BY GROUP_ID

ORDER BY GROUP_ID

 

我们可以看到，在使用了 START WITH … 语句后，并没有使问题简化。虽然递归查询之后的结果集中，按顺序返回了每个机构的所有上级记录。但是 SQL 中的集合是无序的，我们需要自己加上行号，再通过与相邻行的比较计算出每组的初始位置。另外，SQL 中的 GROUP BY 也只支持等值分组，我们只能再增加分组标记用于分组，如果像 SPL 一样支持条件变化分组（当 PARENT_ID=0 时分组）就能简单许多。

 

对于既不支持 WITH，也没有提供类似 START WITH … 方法的数据库来说，SQL 语句就无法实现递归查询了，只能使用存储过程自己实现递归函数，这里就不做详细说明了。

 

SPL的解决方案：

    在 SPL 中提供了函数 A.prior(F) 用于递归查找引用，默认查找所有引用。

	A
1	=T("Organization.txt")
2	>A1.switch(PARENT_ID,A1:ID)
3	=A1.new(ID,ORG_NAME,~.prior(PARENT_ID).len():LEVEL)

A1：从文件中导入组织机构表。

A2：将父机构 ID 外键对象化，转换为相应的父机构记录，实现自连接。

A3：创建由序号、部门名称和级别构成的新表。其中部门级别，是通过函数 A.prior() 递归查找引用记录的层次数量计算得出。

 

    我们可以看到，实现递归问题的 SPL 脚本非常简洁。这是因为 SPL 的递归更加符合逻辑，函数 A.prior() 会返回当前机构的所有父机构的记录组成的集合，接下来无论是计数还是进行其他复杂运算，都能轻松的解决。

 

SPL同样也支持从数据库中读取数据表，比如A1可以改为：

	A
1	=connect("db").query("SELECT * FROM ORGANIZATION")

 

二． 递归查找引用直到指定值

【例 2】 下面是某公司组织结构表，查询北京分公司的下属机构，并列出其上级机构名称，多层的用逗号分隔。

ID	ORG_NAME	PARENT_ID
1	Head Office	0
2	Beijing Branch Office	1
3	Shanghai Branch Office	1
4	Chengdu Branch Office	1
5	Beijing R&D Center	2
…	…	…

 

SQL的解决方案：

    经过前面的分析，我们的直观想法是，每个机构在递归查找上级机构时，如果查找到指定值（例如北京分公司）则停止递归并保留当前机构，查找不到的机构则过滤掉。在 SQL 中，我们很难在一次递归中实现这个目标。我们将问题拆分为两步：首先找到北京分公司的所有下级机构，再按照上一个例题的方法，循环递归查找这些机构的所有父机构，查找到北京分公司时停止。SQL 语句如下：

 

WITH CTE1 (ID,ORG_NAME,PARENT_ID) AS(

   SELECT

      ID,ORG_NAME,PARENT_ID

   FROM ORGANIZATION

   WHERE ORG_NAME='Beijing Branch Office'

   UNION ALL

   SELECT

      ORG.ID,ORG.ORG_NAME,ORG.PARENT_ID

   FROM ORGANIZATION ORG

   INNER JOIN CTE1

   ON ORG.PARENT_ID=CTE1.ID

)

,CTE2 (ID,ORG_NAME,PARENT_ID,O_ID,GROUP_NUM) AS(

   SELECT

      ID,ORG_NAME,PARENT_ID,ID O_ID,1 GROUP_NUM

   FROM CTE1

   UNION ALL

   SELECT ORG.ID,ORG.ORG_NAME,ORG.PARENT_ID,

      CTE2.O_ID,CTE2.GROUP_NUM+1 GROUP_NUM

   FROM ORGANIZATION ORG

   INNER JOIN CTE2

   ON ORG.ID=CTE2.PARENT_ID AND

   CTE2.ORG_NAME<>'Beijing Branch Office'

)

SELECT

   MAX(O_ID) ID, MAX(O_ORG_NAME) ORG_NAME,

   MAX(PARENT_NAME) PARENT_NAME

FROM(

   SELECT

      O_ID, O_ORG_NAME,

      WM_CONCAT(ORG_NAME) OVER

      (PARTITION BY O_ID ORDER BY O_ID,GROUP_NUM) PARENT_NAME

   FROM(

      SELECT

         ID,PARENT_ID,O_ID,GROUP_NUM,

         CASE WHEN GROUP_NUM=1 THEN NULL ELSE ORG_NAME END ORG_NAME,

         CASE WHEN GROUP_NUM=1 THEN ORG_NAME ELSE NULL END O_ORG_NAME

      FROM (

         SELECT

            ID,ORG_NAME,PARENT_ID,O_ID,GROUP_NUM,ROWNUM RN

         FROM CTE2

         ORDER BY O_ID,GROUP_NUM

      )

   )

)

GROUP BY O_ID

ORDER BY O_ID

 

在 ORACLE 中，我们还可以使用 START WITH … CONNECT BY … PRIOR … 进行递归查询，语句如下：

 

WITH CTE1 AS (

   SELECT ID,ORG_NAME,PARENT_ID,ROWNUM RN

   FROM ORGANIZATION ORG

   START WITH ORG.ORG_NAME='Beijing Branch Office'

   CONNECT BY ORG.PARENT_ID=PRIOR ORG.ID

)

,CTE2 AS (

   SELECT

      ID,ORG_NAME,PARENT_ID,RN,

      CASE WHEN LAG(ORG_NAME,1) OVER(ORDER BY RN ASC)= 'Beijing Branch Office' OR

      LAG(ORG_NAME,1) OVER(ORDER BY RN ASC) IS NULL THEN 1 ELSE 0 END FLAG

   FROM(

      SELECT ID,ORG_NAME,PARENT_ID,ROWNUM RN

      FROM CTE1

      START WITH 1=1

      CONNECT BY CTE1.ID=PRIOR CTE1.PARENT_ID

   )

)

SELECT

   MAX(ID) ID, MAX(O_ORG_NAME) ORG_NAME,

   MAX(PARENT_NAME) PARENT_NAME

FROM(

   SELECT

      ID,O_ORG_NAME,GROUP_ID,

      WM_CONCAT(ORG_NAME) OVER

      (PARTITION BY GROUP_ID ORDER BY RN) PARENT_NAME

   FROM(

      SELECT

         ID, ORG_NAME, O_ORG_NAME,RN,

         SUM(ID) OVER (ORDER BY RN) GROUP_ID

      FROM(

         SELECT

            PARENT_ID,RN,

            CASE WHEN FLAG=1 THEN NULL ELSE ORG_NAME END ORG_NAME,

            CASE WHEN FLAG=1 THEN ID ELSE NULL END ID,

            CASE WHEN FLAG=1 THEN ORG_NAME ELSE NULL END O_ORG_NAME

         FROM CTE2

      )

   )

)

GROUP BY GROUP_ID

ORDER BY GROUP_ID

 

SPL的解决方案：

    在 SPL 中提供了函数 A.prior(F,r) 用于递归查找引用直到指定值：

	A
1	=T("Organization.txt")
2	>A1.switch(PARENT_ID,A1:ID)
3	=A1.select@1(ORG_NAME=="Beijing Branch Office")
4	=A1.new(ID,ORG_NAME,~.prior(PARENT_ID,A3) :PARENT_NAME)
5	=A4.select(PARENT_NAME!=null)
6	=A5.run(PARENT_NAME=PARENT_NAME.(PARENT_ID.ORG_NAME).concat@c())

A1：导入组织机构表

A2：将父机构 ID 外键对象化，转换为相应的父机构记录，实现外键对象化。

A3：选出北京分公司的记录。

A4：创建由序号、部门名称和所有上级部门的记录集合组成的表。

A5：选出父机构不为空的记录，即北京分公司的记录。

A6：循环将父机构名称拼成由逗号分隔的字符串。

 

    SPL的解决方案依然非常简洁，使用北京分公司的记录作为参数，用于在递归时查找引用直到北京分公司记录为止。与 SQL 相比，SPL 的逻辑看起来非常清晰。

 

三． 递归查找叶子记录

 

【例 3】 在中国行政区划表中，查询河北省下属区县。部分数据如下：

ID	NAME	PARENT_ID
1	China	0
11	Beijing	1
12	Tianjin	1
13	Hebei	1
…	…	…
1301	Shijiazhuang	13
1302	Tangshan	13
…	…	…

 

SQL的解决方案：

 

    首先我们查找所有从属于河北省的记录，然后在这些记录中查找那些不是其他区域的父区域的记录。SQL 语句如下：

 

WITH CTE1 (ID,NAME,PARENT_ID,PARENT_NAME) AS(

   SELECT

      ID,NAME,PARENT_ID,NULL PARENT_NAME

   FROM CHINA_REGION

   WHERE NAME='Hebei'

   UNION ALL

   SELECT

      T.ID,T.NAME,T.PARENT_ID,CTE1.NAME PARENT_NAME

   FROM CHINA_REGION T

   INNER JOIN CTE1

   ON T.PARENT_ID=CTE1.ID

)

SELECT ID,NAME,PARENT_NAME

FROM CTE1 T1

WHERE NOT EXISTS(

   SELECT 1

   FROM CTE1 T2

   WHERE T1.ID=T2.PARENT_ID

)

ORDER BY ID

 

SPL的解决方案：

    在 SPL 中提供了函数 P.nodes@d(F,r) 用于递归查找所有叶子：

	A
1	=T("ChinaRegion.csv")
2	>A1.switch(PARENT_ID,A1:ID)
3	=A1.select@1(NAME=="Hebei")
4	=A1.nodes@d(PARENT_ID,A3)
5	=A4.new(ID,NAME,PARENT_ID.NAME:PARENT_NAME)

A1：导入中国行政区划表

A2：将父行政区 ID 外键对象化，转换为相应的父行政区记录，实现外键对象化。

A3：选出河北省的记录。

A4：使用函数 P.nodes() 进行递归查找，其中选项 @d 时递归查找所有叶子。

A5：生成由序号、行政区名称和上级行政区名称组成的表。

 

四． 遍历目录下所有文件

 

【例 4】 某小学在线教学终端调查表的汇总整理，统计各终端占比。文件目录结构如下：

目录中的调查文件是 EXCEL 格式，部分数据如下：

ID	STUDENT_NAME	TERMINAL
1	Rebecca   Moore	Phone
2	Ashley Wilson	Phone,PC,Pad
3	Rachel Johnson	Phone,PC,Pad
4	Emily Smith	PC,Pad
5	Ashley Smith	PC
6	Matthew Johnson	Phone
7	Alexis Smith	Phone,PC
8	Megan Wilson	Phone,PC,Pad
…	…	…

 

    由于 SQL 语句不能用于目录和文件的读取，这里就不给出 SQL 的解决方案了，我们看一下 SPL 是如何解决目录和文件的递归遍历问题的。

 

SPL的解决方案：

    在 SPL 中提供了函数directory@s()用于递归查找所有所有子目录下的文件名：

	A
1	=directory@ps("C:/Primary School")
2	>A1.run(t=T(~),@+=t.len(),~=t.conj(TERMINAL.split@c()))
3	=A1.conj().groups(~:TERMINAL;count(~)/A2:PERCENTAGE)

A1：使用函数directory()导入文件目录，其中选项 @s 用于递归查找所有子目录下的文件名

A2：循环读取文件，将终端按逗号拆分并求合集。

A3：将所有的终端分组汇总每种终端的百分比。

 

五． JSON文件递归合并字段值

 

【例 5】 下面是某时刻，新冠状病毒世界各地确诊人数的 JSON 数据，要统计世界确诊人数。文件部分数据如下：

 

[

   {Region:"USA",Confirmed:[

      {Region:"California",Confirmed:3671902},

      {Region:"New York",Confirmed:1139740},

      {Region:"Virginia",Confirmed:620801},

      {Region:"Florida",Confirmed:2064525},

      …

   ]},

   {Region:"Brazil",Confirmed:[…]},

   {Region:"India",Confirmed: […]},

   {Region:"France",Confirmed: […]}

   …

]

 

    由于 SQL 语句不能用于 JSON 文件的读取，这里就不给出 SQL 的解决方案了，我们看一下 SPL 是如何解决 JSON 数据文件内容的递归遍历问题的。

 

SPL的解决方案：

    在 SPL 中提供了函数 A.field@r()用于递归获取字段值，函数 A.conj@r() 用于递归合并序列成员。SPL 脚本如下：

	A
1	=json(file("COVID-19.json").read())
2	=A1.field@r("Confirmed")
3	=A2.conj@r().sum()

A1：导入 JSON 数据文件。

A2：递归获取所有确诊字段值。

A3：递归合并所有确诊人数并求和。

 

总结

经过上面的讨论，我们可以看到，SQL 虽然提供了实现递归问题的方法，但是使用起来却不简单。这是因为 SQL 中没有显式的记录、引用这些概念，返回的递归结果只是靠行号来标识上下级关系。而 SQL 中的集合又是无序的，这使得递归后续的运算非常麻烦。

SPL支持异构的数据结构，并且有显示的记录概念。更重要的是，SPL 处理递归问题的思路非常清晰，自连接后使用递归函数，再进行集合运算即可。SPL 所提供的递归功能要更加灵活，适应性也更加广泛，可以用于很常见的递归目录、文件内容递归等应用场景。

    另外，当查询比较复杂时，SQL 语句的复杂程度会成倍增加。比如经常要用到临时表、嵌套查询等等，使得 SQL 语句的编写和维护难度提升。而 SPL 只要按自然思维去组织计算逻辑，逐行书写出简洁的代码。

esProc 是专业的数据计算引擎，基于有序集合设计，同时提供了完善的集合运算，相当于 Java 和 SQL 优势的结合。在 SPL 的支持下，递归运算会非常容易。

Organization.txt

ChinaRegion.csv

SQL 与 SPL 对比系列：
SQL 和 SPL 的集合运算对比
SQL 和 SPL 的选出运算对比
SQL 和 SPL 的有序运算对比
SQL 和 SPL 的等值分组对比
SQL 和 SPL 的非等值分组对比
SQL 和 SPL 的有序分组对比
SQL 和 SPL 的一对一和一对多连接对比
SQL 和 SPL 的多对一连接对比
SQL 和 SPL 的多对多连接对比
SQL 和 SPL 的基本静态转置对比
SQL 和 SPL 的复杂静态转置对比
SQL 和 SPL 的动态转置对比
SQL 和 SPL 的递归对比