递归¶

对于大多数人来说，递归非常难以理解，因为人脑的限制，当我们思考递归过程时，非常容易“爆栈”。不过，我们可以通过下地下室取东西来类比递归：

我们从地面开始下地下室，每到达一层都有 3 种选择：
- 把东西打包好带上 → 前序遍历（已知当前层，未知后续层）
- 先把东西打包好，等到返回地面时再带走 → 中序遍历（仅限 BST）
- 在触底返回时打包带走 → 后序遍历（已知所有走过的路）
触底时开始返回
返回地面时，我们取回所有所需物品，递归结束。

在这个过程中，我们在每层重复的动作就是递归中的最小重复单元（这就是我们编写的递归代码），而触底返回，就是递归的终止条件。所以我们编写递归时，只要抓住了最小重复单元和终止条件，递归就迎刃而解了。

_{递归的地下室类比}

🕳️ 地面
└─ 👣 第 1 层：factorial(3)
   └─ 👣 第 2 层：factorial(2)
      └─ 👣 第 3 层：factorial(1)
         └─ 🎯 触底：factorial(0)
             ↓
         ┌─ ✅ 返回 1（终止条件）
      ┌─ 🔙 返回 1 × 1 = 1
   ┌─ 🔙 返回 2 × 1 = 2
┌─ 🔙 返回 3 × 2 = 6
🌟 最终结果：6

_{3! 递归调用栈示意图}

如何写出递归？¶

递归的本质是将大问题拆解为相似的小问题。编写递归时，可以遵循以下步骤：

确定递归函数的输入和输出（函数签名）
确定终止条件（Base Case）
- 链表 / 树：节点为 None 或 null 时
- 数组 / 字符串：索引超出边界（如 low > high），或者长度为 0
- 数值计算：n == 0 或 n == 1 时
确定最小重复单元：
递推关系：如何将问题拆解为子问题
处理逻辑：在递归调用前/后做什么（前序 vs 后序）

Tip

只要递归状态从 0 开始，数组就要多开 1 个以避免越界访问，如动态规划和前缀和。

经典题目¶

实战应用：扁平列表转树形结构¶

在实际业务中，数据库通常以扁平结构存储层级数据（如省市区、部门组织），每条记录通过 parent_id 指向父节点。API 层需要将其重组为树形结构以供前端渲染。这是递归在工程中最典型的应用场景之一。

数据结构定义如下：

type Area struct {
    ID       int     `json:"id"`
    ParentID int     `json:"parent_id"`
    Name     string  `json:"name"`
    Level    int     `json:"level"`
    Children []*Area `json:"children,omitempty"`
}

测试数据：

flatData := []*Area{
    {ID: 1, ParentID: 0, Name: "广东省", Level: 1},
    {ID: 2, ParentID: 0, Name: "浙江省", Level: 1},
    {ID: 3, ParentID: 1, Name: "广州市", Level: 2},
    {ID: 4, ParentID: 1, Name: "深圳市", Level: 2},
    {ID: 5, ParentID: 2, Name: "杭州市", Level: 2},
    {ID: 6, ParentID: 3, Name: "天河区", Level: 3},
    {ID: 7, ParentID: 3, Name: "番禺区", Level: 3},
    {ID: 8, ParentID: 6, Name: "猎德街道", Level: 4},
    {ID: 9, ParentID: 8, Name: "猎德村", Level: 5},
}

方法一：递归（\(O(n^2)\)）¶

思路直观：对每个节点，递归地从整个列表中筛选出其子节点，直到叶子节点为止（Base Case：当前节点无子节点，返回空切片）。

// BuildTreeRecursive 递归构建树形结构
// 每一层都需要线性扫描完整列表，时间复杂度 O(n^2)
func BuildTreeRecursive(areas []*Area, parentID int) []*Area {
    var tree []*Area

    for _, area := range areas {
        if area.ParentID == parentID {
            area.Children = BuildTreeRecursive(areas, area.ID) // 递归挂载子节点
            tree = append(tree, area)
        }
    }

    return tree
}

// 调用：从 parentID=0 的顶级节点开始构建
tree := BuildTreeRecursive(flatData, 0)

方法二：哈希表（\(O(n)\)）¶

递归方案的瓶颈在于：每处理一个节点都要线性扫描整个列表。优化思路是先用哈希表建立 ID → 节点 的映射，将子节点查找从 \(O(n)\) 降为 \(O(1)\)，整体只需两次线性遍历。

// BuildTreeHashMap 使用哈希表构建树形结构
// 两次线性遍历，时间复杂度 O(n)
func BuildTreeHashMap(areas []*Area) []*Area {
    var roots []*Area
    areaMap := make(map[int]*Area, len(areas))

    // 第一次遍历：建立 ID → 节点 的映射
    for _, area := range areas {
        areaMap[area.ID] = area
    }

    // 第二次遍历：将每个节点挂载到其父节点上
    for _, area := range areas {
        if area.ParentID == 0 {
            roots = append(roots, area) // 顶级节点直接收集
            continue
        }
        if parent, ok := areaMap[area.ParentID]; ok {
            parent.Children = append(parent.Children, area)
        }
    }

    return roots
}

递归¶