深度解析：递归查询与迭代查询核心原理与实践

一、什么是递归查询

递归查询（Recursion）是指在函数或查询过程中，函数体内部直接或间接调用自身，将复杂问题不断拆分为更小的同类子问题，直到满足终止条件后依次返回结果。它常见于树/图遍历、分治算法，以及 SQL 中的递归公共表表达式（CTE）等场景。

• 核心要素

  1. 终止条件：防止无限递归；
  2. 简单情境：满足终止条件时的直接返回；
  3. 规模缩减：每次递归调用时，将问题规模逐步减小。

应用示例：SQL 递归 CTE

WITH MenuTree AS (
  SELECT Id, ParentId, Name
  FROM base_permission
  WHERE ParentId = 0           -- 初始查询
  UNION ALL
  SELECT p.Id, p.ParentId, p.Name
  FROM base_permission p
  JOIN MenuTree m
    ON p.ParentId = m.Id       -- 递归引用自身
)
SELECT * FROM MenuTree;

上例中，CTE 会反复自引用，直到没有新的记录加入为止，形成完整层级数据 (Microsoft Learn)。
性能分析：若树的最大深度为 D，基表记录数为 N，则总时间复杂度约为 O(D×N)；空间复杂度与最终结果集 M 线性相关 (yanfukun.com)。

二、什么是迭代查询

迭代查询（Iteration）则是通过循环结构（如 for、while）或显式队列/栈，重复执行同一段逻辑，直到满足特定的退出条件。它不会产生调用栈的额外开销，常用于需要明显控制流程、或循环次数已知的场景。

• 常见形式

  • for 循环：适用于已知迭代次数；
  • while 循环：条件更灵活，可动态更新；
  • 显式队列/栈：用于广度/深度优先遍历等。

应用示例：Python 计算阶乘

def factorial_iter(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

三、性能对比

四、实践案例：DFS 的两种实现

以二叉树深度优先搜索（Depth-First Search, DFS）为例：

递归版

def dfs_recursive(node):
    if not node:
        return
    visit(node)
    dfs_recursive(node.left)
    dfs_recursive(node.right)

迭代版

def dfs_iterative(root):
    stack = [root]
    while stack:
        node = stack.pop()
        if not node:
            continue
        visit(node)
        stack.append(node.right)
        stack.append(node.left)

五、何时选择

• 递归

  • 问题具有天然的分治特性（如树/图遍历、回溯算法）；
  • 代码可读性和维护性优先；

• 迭代

  • 对空间开销敏感，需避免深度过大的调用；
  • 流程控制明确、迭代次数已知；

结语

递归查询与迭代查询各有优势与局限，理解它们的原理和适用场景，是编程与数据库实践中的必备技能。希望本文帮助学生初学者在算法思维和 SQL 应用上更进一步！