1.引言

递归在编程中是处理问题的重要方法，但递归同时有着反直觉的思考逻辑，本文将对其进行简单介绍并举例

# 语法
WITH RECURSIVE cte_name(n1,n2...) AS
# n是初始条件中SELECT中各列的别名
(SELECT...
# 初始条件
UNION
SELECT...)
# 递归主体及终止条件
SELECT * FROM cte_name;
# 调用递归

WITH RECURSIVE cte_name AS
# 如果未在开头声明初始条件SELECT的列别名，那就需要在初始条件中指定别名（如果递归主体中需要基于此的计算字段）
(SELECT...
# 初始条件
UNION
SELECT...)
# 递归主体及终止条件
SELECT * FROM cte_name;
# 调用递归

2.简单应用

2.1.序号

# 序号：1，2，3，4，5...
# 每一项都等于前一项+1
WITH RECURSIVE cte_cnt AS
(SELECT 1 AS n
# 初始化
UNION
SELECT n+1
# 递归主体
FROM cte_cnt
WHERE n<5)
# 终止条件
SELECT n FROM cte_cnt;
# 调用递归

2.2.阶乘

# 1，2，6，24，120...
# 1，2，3，4，5
# 每一项都等于前一项乘以当前项序号
WITH RECURSIVE cte_fac(num,sum) AS
(SELECT
	1,
# 初始化
	1
UNION
SELECT
	num+1,
	sum*(num+1)
# 递归主体
FROM cte_fac
WHERE num<5)
# 终止条件
SELECT * FROM cte_fac;
# 调用递归

2.3.斐波那契数列

# 斐波那契数列：1，1，2，3，5，8，13，21...
# 观察可知从第三项起，每一项都等于前两项之和

WITH RECURSIVE cte_fib(num,pre,cur) AS
(SELECT
	1 AS num,
	1 AS pre,
	1 AS cur
UNION
SELECT
	num+1 AS num,
	# 序号增加
	cur AS pre,
	# 令前一项等于当前项
	cur+pre AS cur
	# 令当前项等于前一项与当前项之和
FROM cte_fib
WHERE num<10)
SELECT * FROM cte_fib;

3.邻接表模型

3.1.数据源

# 创建邻接表模型：外键就在本表的列上
CREATE TABLE IF NOT EXISTS category (
  id int(10) AUTO_INCREMENT,
  title varchar(255) NOT NULL,
  parent_id int(10) unsigned DEFAULT NULL,
  PRIMARY KEY (id),
  FOREIGN KEY (parent_id) REFERENCES category (id) 
  ON DELETE CASCADE ON UPDATE CASCADE); 
# 插入数据
INSERT INTO category(title,parent_id)
VALUES('Electronics',NULL);
INSERT INTO category(title,parent_id) 
VALUES('Laptops & PC',1);
INSERT INTO category(title,parent_id) 
VALUES('Laptops',2);
INSERT INTO category(title,parent_id) 
VALUES('PC',2);
INSERT INTO category(title,parent_id) 
VALUES('Cameras & photo',1);
INSERT INTO category(title,parent_id) 
VALUES('Camera',5);
INSERT INTO category(title,parent_id) 
VALUES('Phones & Accessories',1);
INSERT INTO category(title,parent_id) 
VALUES('Smartphones',7);
INSERT INTO category(title,parent_id) 
VALUES('Android',8);
INSERT INTO category(title,parent_id) 
VALUES('iOS',8);
INSERT INTO category(title,parent_id) 
VALUES('Other Smartphones',8);
INSERT INTO category(title,parent_id) 
VALUES('Batteries',7);
INSERT INTO category(title,parent_id) 
VALUES('Headsets',7);
INSERT INTO category(title,parent_id) 
VALUES('Screen Protectors',7); 

3.2.基础查询

# 根节点：没有父节点的节点
# 子节点：父节点是根节点的节点
# 叶子节点：没有子节点的节点

# 查看根节点，相关应用：查看最高层管理者
SELECT * 
FROM category 
WHERE parent_id IS NULL;
# 查看子节点，相关应用：查看某一管理者下属员工
SELECT * 
FROM category 
WHERE parent_id=1;
# 查看叶子节点，相关应用：查看非管理者的员工
SELECT * 
FROM 
	category AS CF 
	# 作为父节点的表
	LEFT JOIN category AS CS 
	# 作为子节点的表
	ON CF.id=CS.parent_id 
	# 父表的id=子表的父id
WHERE CS.id IS NULL;
# 某一节点的子节点id为空则意味着该节点就是叶子节点

3.3.递归查询

3.3.1查看整棵树

WITH RECURSIVE cte_allpath(id,path) AS
(SELECT
	id,
	title
FROM category
WHERE parent_id IS NULL
# 初始条件为根节点
UNION
SELECT
	CS.id,
	CONCAT(CF.path,'>',CS.title)
	# 递归过程
FROM
	cte_allpath AS CF 
	INNER JOIN category AS CS # 必须为内联接，否则将无限递归
	ON CF.id=CS.parent_id) # 注意此处联接条件，以递归作为父表进行进行联接
	# 终止条件为空表
SELECT * FROM cte_allpath;

3.3.2.查看指定子树

WITH RECURSIVE cte_allpath(id,path) AS
(SELECT
	id,
	title
FROM category
WHERE id=7
# 初始条件
UNION
SELECT
	CS.id,
	CONCAT(CF.path,'>',CS.title)
	# 递归过程
FROM
	cte_allpath AS CF 
	INNER JOIN category AS CS # 必须为内联接，否则将无限递归
	ON CF.id=CS.parent_id) # 注意此处联接条件，以递归作为父表进行进行联接
	# 终止条件为空表
SELECT * FROM cte_allpath;

3.3.3.查看指定路径

WITH RECURSIVE cte_allpath(id,parent_id,path) AS
(SELECT 
	id,
	parent_id,
	title
FROM category
WHERE id=10
# 初始条件为指定节点
UNION
SELECT
	CF.id,
	CF.parent_id,
	CF.title
	# 递归过程
FROM
	cte_allpath AS CS
	INNER JOIN category AS CF # 必须为内联接，否则将无限递归
	ON CS.parent_id=CF.id) # 注意此处联接条件，以递归作为子表进行进行联接
	# 终止条件为空表
SELECT * FROM cte_allpath;

3.3.4.给遍历过程增加序号

WITH RECURSIVE cte_allpath AS
(SELECT
	id,
	title AS path,
	@PATH_NUM:=1
FROM category 
WHERE parent_id IS NULL 
UNION
SELECT
	CS.id,
	CONCAT(CF.path, '>', CS.title),
	@PATH_NUM:=@PATH_NUM+1
FROM cte_allpath AS CF
JOIN category AS CS
ON CF.id = CS.parent_id)
SELECT * FROM cte_allpath;

3.3.5.给遍历过程增加层号

WITH RECURSIVE cte_allpath AS
(SELECT
	id,
	title AS path,
	1 AS level
FROM category 
WHERE parent_id IS NULL 
UNION
SELECT
	CS.id,
	CONCAT(CF.path, '>', CS.title),
	level+1
FROM cte_allpath AS CF
JOIN category AS CS
ON CF.id = CS.parent_id)
SELECT * FROM cte_allpath;

4.总结

不应该纠结多层递归的每一步如何执行

递归通常只关注初始条件，递归主体，终止条件

初始条件：决定递归的开始

递归主体：一次求解过程（该求解过程具有递归性：即引用了其自身）

终止条件：决定递归的结束，在查询中本质上是递归主体SELECT前的过程返回了空表

5.拓展（高级）

# 要明白此过程需要有一定的DDL（数据定义）的基础

# 创建临时表
CREATE TEMPORARY TABLE IF NOT EXISTS hanoi_step(
id INT PRIMARY KEY AUTO_INCREMENT,
step CHAR(15));
# 创建存储过程
DELIMITER $$
CREATE PROCEDURE IF NOT EXISTS hanoi(IN n INT,IN from_col CHAR(5),IN assist_col CHAR(5),IN to_col CHAR(5))
BEGIN
IF 
	n=1 # 如果只有一层，直接从出发柱移动到目的柱
THEN
	INSERT INTO hanoi_step(step) SELECT CONCAT(from_col,'->',to_col);# 将过程存入临时表
ELSE
	# 否则：先将出发柱上面的n-1层移到辅助柱
    CALL hanoi(n-1,from_col,to_col,assist_col);
	# 再将出发柱最后一层移到目的柱
    INSERT INTO hanoi_step(step) SELECT CONCAT(from_col,'->',to_col);# 将过程存入临时表
	# 最后将辅助柱的n-1层移到目的柱
    CALL hanoi(n-1,assist_col,from_col,to_col);
END IF;
END
$$
DELIMITER ;
# 设置存储过程的递归深度，若实际递归超过允许最大深度将报错，系统默认深度为0
SET @@session.max_sp_recursion_depth=100;
# 清空临时表
TRUNCATE hanoi_step;
# 调用存储过程
CALL hanoi(5,'A','B','C');
# 查看临时表
SELECT * FROM hanoi_step;
# 删除临时表
DROP TEMPORARY TABLE IF EXISTS hanoi_step;
# 删除存储过程
DROP PROCEDURE IF EXISTS hanoi;

更多知识见专栏