概述

最近刷題時遇到了一道需要根據組織層級來統計各個層級的一些數據，當時碰到時的第一想法就是需要使用遞歸來實現。但是以前在SQl中從來就沒有用過遞歸查詢，后面到網上一搜索，居然還真有遞歸查詢的實現，也算是給自己掃了一下盲了。

SQL 中的遞歸實現

遞歸是一種通過自身調用自身來 逐步推理出計算結果的一種思想。在SQL中遞歸查詢同樣也是如此，通過自身調用自身來逐步構建查詢結果。一般多用于處理具有層次結構的數據，如樹形結構、組織結構圖、文件系統目錄等。
在SQL中，使用 WITH RECURSIVE 關鍵字來實現。

同編程語言中的遞歸函數調用類似，遞歸查詢的執行過程也需要遵循以下三個原則：

• 初始查詢
  首次執行初始查詢 ，得到一個初始結果集。
• 遞歸調用
  將初始結果集作為輸入，執行遞歸查詢，并將遞歸查詢的結果與初始結果集合并，作為下一次查詢的輸入。
• 終止條件
  重復執行遞歸查詢，直到沒有新的行可以添加到結果集中，遞歸查詢終止。
  遞歸查詢的語法如下：

    WITH RECURSIVE table_name AS (--初始查詢SELECT 1 AS level FROM XXX WHERE XXXUNION ALL--遞歸查詢SELECT level+1  FROM table_name WHERE XXXX--終止條件是查詢到所有的記錄都做了處理，遞歸終止 )

例如使用遞歸生成一個連續的序列：

-- 遞歸查詢生成數字序列
WITH RECURSIVE lianxu_numbers AS (-- 初始查詢，生成第一個數字 1SELECT 1 AS numUNION ALL-- 遞歸查詢（遞歸成員）：生成下一個數字SELECT num + 1FROM lianxu_numbersWHERE num < 100 -- 小于100 是終止條件
)
SELECT * FROM numbers;

題目一:分析組織層級

表：Employees+----------------+---------+
| Column Name    | Type    | 
+----------------+---------+
| employee_id    | int     |
| employee_name  | varchar |
| manager_id     | int     |
| salary         | int     |
| department     | varchar |
+----------------+----------+
employee_id 是這張表的唯一主鍵。
每一行包含關于一名員工的信息，包括他們的 ID，姓名，他們經理的 ID，薪水和部門。
頂級經理（CEO）的 manager_id 是空的。
編寫一個解決方案來分析組織層級并回答下列問題：層級：對于每名員工，確定他們在組織中的層級（CEO 層級為 1，CEO 的直接下屬員工層級為 2，以此類推）。
團隊大小：對于每個是經理的員工，計算他們手下的（直接或間接下屬）總員工數。
薪資預算：對于每個經理，計算他們控制的總薪資預算（所有手下員工的工資總和，包括間接下屬，加上自己的工資）。
返回結果表以 層級 升序 排序，然后以預算 降序 排序，最后以 employee_name 升序 排序。結果格式如下所示。示例：輸入：Employees 表：+-------------+---------------+------------+--------+-------------+
| employee_id | employee_name | manager_id | salary | department  |
+-------------+---------------+------------+--------+-------------+
| 1           | Alice         | null       | 12000  | Executive   |
| 2           | Bob           | 1          | 10000  | Sales       |
| 3           | Charlie       | 1          | 10000  | Engineering |
| 4           | David         | 2          | 7500   | Sales       |
| 5           | Eva           | 2          | 7500   | Sales       |
| 6           | Frank         | 3          | 9000   | Engineering |
| 7           | Grace         | 3          | 8500   | Engineering |
| 8           | Hank          | 4          | 6000   | Sales       |
| 9           | Ivy           | 6          | 7000   | Engineering |
| 10          | Judy          | 6          | 7000   | Engineering |
+-------------+---------------+------------+--------+-------------+
輸出：+-------------+---------------+-------+-----------+--------+
| employee_id | employee_name | level | team_size | budget |
+-------------+---------------+-------+-----------+--------+
| 1           | Alice         | 1     | 9         | 84500  |
| 3           | Charlie       | 2     | 4         | 41500  |
| 2           | Bob           | 2     | 3         | 31000  |
| 6           | Frank         | 3     | 2         | 23000  |
| 4           | David         | 3     | 1         | 13500  |
| 7           | Grace         | 3     | 0         | 8500   |
| 5           | Eva           | 3     | 0         | 7500   |
| 9           | Ivy           | 4     | 0         | 7000   |
| 10          | Judy          | 4     | 0         | 7000   |
| 8           | Hank          | 4     | 0         | 6000   |
+-------------+---------------+-------+-----------+--------+
解釋：組織結構：
Alice（ID：1）是 CEO（層級 1）沒有經理。
Bob（ID：2）和 Charlie（ID：3）是 Alice 的直接下屬（層級 2）
David（ID：4），Eva（ID：5）從屬于 Bob，而 Frank（ID：6）和 Grace（ID：7）從屬于 Charlie（層級 3）
Hank（ID：8）從屬于 David，而 Ivy（ID：9）和 Judy（ID：10）從屬于 Frank（層級 4）
層級計算：
CEO（Alice）層級為 1
每個后續的管理層級都會使層級數加 1
團隊大小計算：
Alice 手下有 9 個員工（除她以外的整個公司）
Bob 手下有 3 個員工（David，Eva 和 Hank）
Charlie 手下有 4 個員工（Frank，Grace，Ivy 和 Judy）
David 手下有 1 個員工（Hank）
Frank 手下有 2 個員工（Ivy 和 Judy）
Eva，Grace，Hank，Ivy 和 Judy 沒有直接下屬（team_size = 0）
預算計算：
Alice 的預算：她的工資（12000）+ 所有員工的工資（72500）= 84500
Charlie 的預算：他的工資（10000）+ Frank 的預算（23000）+ Grace 的工資（8500）= 41500
Bob 的預算：他的工資 (10000) + David 的預算（13500）+ Eva 的工資（7500）= 31000
Frank 的預算：他的工資 (9000) + Ivy 的工資（7000）+ Judy 的工資（7000）= 23000
David 的預算：他的工資 (7500) + Hank 的工資（6000）= 13500
沒有直接下屬的員工的預算等于他們自己的工資。
注意：結果先以層級升序排序
在同一層級內，員工按預算降序排序，然后按姓名升序排序

題解

with recursive a1 as (select employee_id,manager_id,1 as afrom employeesunion allselect a1.employee_id,e.manager_id,a+1from employees e  join a1 on a1.manager_id=e.employee_id
)
,
--level：層級
a2 as (select employee_id, count(*) levelfrom a1group by employee_id)/*level*/
,
--下屬人數
a3 as (select manager_id, count(*) team_sizefrom a1where manager_id is not nullgroup by manager_id)/*size*/
,
--工資統計
a4 as (select a1.manager_id, sum(salary) budgetfrom a1left join employees e using (employee_id)where a1.manager_id is not nullgroup by a1.manager_id
)select employee_id,employee_name,level,ifnull(team_size,0) team_size,salary+ifnull(budget,0) budget
from a2 left join employees using(employee_id)
left join a3 on a2.employee_id=a3.manager_id
left join a4 on a2.employee_id=a4.manager_id
order by level,budget desc,employee_name;

題目二:樹節點求解

表：Tree+-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| p_id        | int  |
+-------------+------+
id 是該表中具有唯一值的列。
該表的每行包含樹中節點的 id 及其父節點的 id 信息。
給定的結構總是一個有效的樹。樹中的每個節點可以是以下三種類型之一："Leaf"：節點是葉子節點。
"Root"：節點是樹的根節點。
"lnner"：節點既不是葉子節點也不是根節點。
編寫一個解決方案來報告樹中每個節點的類型。以 任意順序 返回結果表。結果格式如下所示。示例 1：輸入：
Tree table:
+----+------+
| id | p_id |
+----+------+
| 1  | null |
| 2  | 1    |
| 3  | 1    |
| 4  | 2    |
| 5  | 2    |
+----+------+
輸出：
+----+-------+
| id | type  |
+----+-------+
| 1  | Root  |
| 2  | Inner |
| 3  | Leaf  |
| 4  | Leaf  |
| 5  | Leaf  |
+----+-------+
解釋：
節點 1 是根節點，因為它的父節點為空，并且它有子節點 2 和 3。
節點 2 是一個內部節點，因為它有父節點 1 和子節點 4 和 5。
節點 3、4 和 5 是葉子節點，因為它們有父節點而沒有子節點。

題解

步驟一：通過遞歸查詢出每個節點的上級節點和下級節點分布

with recursive a1 AS (select id,p_id, 1 as level from Treeunion allselect a1.id,e.p_id, level+1 as level from Tree e join a1 on a1.p_id = e.id
)
select * from a1;

輸出：

| id | p_id | level |
| -- | ---- | ----- |
| 1  | null | 1     |
| 2  | 1    | 1     |
| 3  | 1    | 1     |
| 4  | 2    | 1     |
| 5  | 2    | 1     |
| 3  | null | 2     |
| 2  | null | 2     |
| 5  | 1    | 2     |
| 4  | 1    | 2     |
| 4  | null | 3     |
| 5  | null | 3     |

得到上面這張零時表后，就可以根據這張臨時表統計出每個節點的下級節點的數量，每個節點所在的層次。

步驟二：分組統計

• 統計節點所在層級

select id, count(*) as level from a1 group by id;

• 統計幾點的下級節點(包括間接節點)的數量

select p_id, count(*) as son_nums from a1 where p_id is not null group by p_id;

子節點數為0的節點就為葉子節點。