深度优先搜索中栈的空间优化及递归转非递归的坑点

一、先搞懂：DFS里的栈和递归到底啥关系

很多刚接触DFS（深度优先搜索）的人，都会有个疑问：为啥递归写DFS这么方便，又要转非递归？栈又在里面起啥作用？其实递归的本质，就是系统帮我们偷偷用了个栈。

举个最常见的例子：遍历一个文件夹里的所有文件。递归写法的逻辑是啥？先打开当前文件夹，读里面的所有内容；如果是子文件夹，就“暂停”当前文件夹的遍历，先去遍历子文件夹；子文件夹遍历完了，再回到刚才暂停的地方，继续遍历当前文件夹剩下的内容。这里的“暂停”和“回来”，系统是用栈存的——把当前没遍历完的文件夹信息（比如当前文件夹路径、已经读到第几个文件）压进栈，等子任务干完了，再从栈里拿出来接着干。

那递归有啥问题？比如你遍历的文件夹有1000层嵌套，系统的栈是有大小限制的（比如Windows下默认栈大小可能只有1MB左右），超过这个限制就会直接报错“栈溢出”。这时候就必须转成非递归，自己手动控制栈，还能顺便优化空间。

1.1 递归转非递归的核心：自己模拟系统栈

系统帮我们干的事，无非是两件：压栈（存当前状态）、弹栈（恢复之前的状态）。转非递归的核心，就是把这两件事自己来做。

先给大家看一个递归的DFS示例，技术栈统一用Python，所有示例都用这个：

# 技术栈：Python
# 递归版DFS：遍历文件夹下所有文件
import os

def dfs_recursive(folder_path):
    # 1. 遍历当前文件夹下的所有内容
    for entry in os.listdir(folder_path):
        # 拼接完整路径
        full_path = os.path.join(folder_path, entry)
        # 2. 如果是文件，直接打印（或处理）
        if os.path.isfile(full_path):
            print(f"找到文件：{full_path}")
        # 3. 如果是文件夹，递归调用（系统自动压栈）
        elif os.path.isdir(full_path):
            dfs_recursive(full_path)

这个代码逻辑很简单，但问题很明显：如果文件夹嵌套太深，比如从A文件夹开始，A里有B，B里有C，一直嵌套到第1000层，运行时就会报RecursionError: maximum recursion depth exceeded（递归深度超过最大限制）。

那怎么转非递归？核心就是自己建一个栈，把“当前要处理的文件夹”压进去，然后循环弹栈处理：

# 技术栈：Python
# 非递归版DFS（基础版）：遍历文件夹下所有文件
import os

def dfs_non_recursive_basic(folder_path):
    # 1. 初始化自己的栈，把根文件夹压进去
    stack = [folder_path]
    # 2. 循环处理栈里的内容，直到栈空
    while stack:
        # 3. 弹出栈顶的文件夹（后进先出，符合DFS的逻辑）
        current_folder = stack.pop()
        # 4. 遍历当前文件夹下的所有内容
        for entry in os.listdir(current_folder):
            full_path = os.path.join(current_folder, entry)
            if os.path.isfile(full_path):
                print(f"找到文件：{full_path}")
            elif os.path.isdir(full_path):
                # 5. 把子文件夹压进栈，后面会被弹出来处理
                stack.append(full_path)

哎？这个代码看起来没问题，但运行一下就会发现坑：遍历的顺序和递归版的不一样！比如当前文件夹下有三个文件夹：A、B、C，递归版会先处理A，再处理A的子文件夹，处理完A的所有内容再处理B；但非递归版因为栈是后进先出，压栈的时候是A、B、C的顺序，弹出来的时候会先弹C，再弹B，最后弹A，顺序完全反了。

1.2 坑点1：栈的顺序搞反，遍历逻辑出错

这是递归转非递归最容易踩的第一个坑：没搞清楚栈“后进先出”的特性，导致遍历顺序和预期不符。那怎么解决？其实很简单，压栈的时候把顺序反过来就行。

比如刚才的例子，当前文件夹下的内容顺序是[A, B, C]，我们压栈的时候改成[C, B, A]，这样弹出来的顺序就变成[A, B, C]，和递归版一致了。修改后的代码：

# 技术栈：Python
# 非递归版DFS（修正顺序版）：遍历文件夹下所有文件
import os

def dfs_non_recursive_fixed_order(folder_path):
    stack = [folder_path]
    while stack:
        current_folder = stack.pop()
        entries = os.listdir(current_folder)
        # 关键：把当前文件夹下的内容逆序后再压栈，保证弹出顺序和递归一致
        for entry in reversed(entries):
            full_path = os.path.join(current_folder, entry)
            if os.path.isfile(full_path):
                print(f"找到文件：{full_path}")
            elif os.path.isdir(full_path):
                stack.append(full_path)

现在运行这个代码，遍历顺序就和递归版完全一样了。但这还只是最基础的转法，栈的空间还能优化吗？

二、栈的空间优化：从“存完整状态”到“存必要信息”

刚才的非递归版，栈里存的是整个文件夹的路径，这看起来没什么问题，但如果我们的DFS需要存更多的状态，比如当前文件夹已经遍历到第几个文件了，那栈里存的内容就会变多，空间占用也会变大。

举个更复杂的例子：假设我们要遍历一个文件夹，并且要统计每个文件夹里的文件数量。递归版的代码是这样的：

# 技术栈：Python
# 递归版：统计每个文件夹的文件数量
import os

def count_files_recursive(folder_path, result=None):
    # 初始化结果字典（第一次调用时创建）
    if result is None:
        result = {}
    # 初始化当前文件夹的文件数量
    current_count = 0
    for entry in os.listdir(folder_path):
        full_path = os.path.join(folder_path, entry)
        if os.path.isfile(full_path):
            current_count += 1
        elif os.path.isdir(full_path):
            # 递归统计子文件夹的文件数量
            sub_count = count_files_recursive(full_path, result)
            current_count += sub_count
    # 把当前文件夹的统计结果存入字典
    result[folder_path] = current_count
    return current_count, result

这个代码的逻辑是：每个文件夹的文件数量，等于自己的文件数量加上所有子文件夹的文件数量。那转成非递归版的时候，栈里需要存什么状态？

我们想一下递归的过程：当处理子文件夹的时候，当前文件夹的处理被暂停，需要记住两个信息：一是当前文件夹的路径，二是当前文件夹已经统计到的文件数量。等子文件夹统计完了，把子文件夹的数量加到当前文件夹的数量里，再继续处理。

那最基础的非递归版，栈里存的是一个元组，包含当前文件夹的路径和当前已经统计的数量：

# 技术栈：Python
# 非递归版（基础状态存储）：统计每个文件夹的文件数量
import os

def count_files_non_recursive_basic(folder_path):
    result = {}
    # 栈里存的是元组：(文件夹路径, 当前已统计的文件数量)
    stack = [(folder_path, 0)]
    while stack:
        current_folder, current_count = stack.pop()
        # 先把当前文件夹的状态压回栈，标记为“未处理完”
        stack.append((current_folder, current_count))
        # 遍历当前文件夹的内容，找子文件夹
        entries = os.listdir(current_folder)
        for entry in reversed(entries):
            full_path = os.path.join(current_folder, entry)
            if os.path.isfile(full_path):
                # 如果是文件，直接更新当前文件夹的数量
                stack[-1] = (current_folder, stack[-1][1] + 1)
            elif os.path.isdir(full_path):
                # 如果是子文件夹，压入栈，等待处理
                stack.append((full_path, 0))
        # 处理完所有内容后，把结果存入字典
        result[current_folder] = current_count
    return result

哎？这个代码运行的时候会有问题：当处理子文件夹的时候，父文件夹的数量还没统计完，结果字典里就会提前存入父文件夹的错误数量。这是因为我们的状态存储不完整，没有标记这个文件夹是“正在处理”还是“已经处理完”。

2.1 坑点2：状态标记缺失，导致逻辑混乱

这是递归转非递归的第二个大坑：递归的时候，系统会自动标记“当前任务是否完成”，但自己写栈的时候，很容易忘记给状态加标记，导致逻辑混乱。

那怎么解决？给栈里的状态加一个标记位，比如用0表示“未处理”，1表示“已处理”。修改后的代码：

# 技术栈：Python
# 非递归版（修正状态标记）：统计每个文件夹的文件数量
import os

def count_files_non_recursive_fixed_state(folder_path):
    result = {}
    # 栈里存的是元组：(标记位, 文件夹路径, 当前已统计的文件数量)
    # 标记位：0=未处理，1=已处理
    stack = [(0, folder_path, 0)]
    while stack:
        mark, current_folder, current_count = stack.pop()
        if mark == 0:
            # 第一次处理这个文件夹：先压回“已处理”的状态，再压入所有子内容
            stack.append((1, current_folder, current_count))
            # 逆序遍历内容，保证顺序正确
            entries = os.listdir(current_folder)
            for entry in reversed(entries):
                full_path = os.path.join(current_folder, entry)
                if os.path.isfile(full_path):
                    # 文件直接加数量
                    stack.append((1, current_folder, current_count + 1))
                elif os.path.isdir(full_path):
                    # 子文件夹压入“未处理”状态
                    stack.append((0, full_path, 0))
        else:
            # 第二次处理这个文件夹：所有子内容都处理完了，存入结果
            result[current_folder] = current_count
    return result

现在这个代码就可以正确统计每个文件夹的文件数量了。但问题又来了：如果文件夹的层级很多，栈里存的状态元组会越来越多，空间占用会不会很大？

其实很多时候，我们不需要存这么多状态。比如在这个例子里，我们需要的是“子文件夹的统计结果”，只要能拿到这个结果，父文件夹的状态就可以简化。比如我们可以用一个额外的字典来存子文件夹的结果，栈里只需要存当前文件夹的路径，这样就能减少栈的空间占用。

2.2 栈空间优化的核心：拆分状态，减少存储

优化栈空间的核心思路是：把“必须实时存储的状态”和“可以事后获取的状态”分开，把可以事后获取的状态从栈里移除，只在栈里存最必要的信息。

比如刚才的统计文件数量的例子，我们可以把“子文件夹的统计结果”存在一个额外的字典里，栈里只存当前文件夹的路径，这样栈的每个元素就从原来的“标记位+路径+数量”变成了“路径”，空间占用减少了三分之二。优化后的代码：

# 技术栈：Python
# 非递归版（栈空间优化）：统计每个文件夹的文件数量
import os

def count_files_non_recursive_optimized(folder_path):
    result = {}
    # 额外的字典：用来暂存子文件夹的统计结果
    sub_result = {}
    # 栈里只存文件夹路径，空间占用大幅减少
    stack = [folder_path]
    while stack:
        current_folder = stack.pop()
        # 检查当前文件夹是否已经处理过（避免重复处理）
        if current_folder in result:
            # 如果已经处理过，说明是子文件夹的结果，加到父文件夹的统计里
            parent_folder = stack[-1]
            sub_result[parent_folder] = sub_result.get(parent_folder, 0) + result[current_folder]
            continue
        # 第一次处理：压回当前文件夹，标记为“未处理”（用结果字典的存在与否来标记）
        stack.append(current_folder)
        # 逆序遍历内容
        entries = os.listdir(current_folder)
        for entry in reversed(entries):
            full_path = os.path.join(current_folder, entry)
            if os.path.isfile(full_path):
                # 文件直接加到子结果里
                sub_result[current_folder] = sub_result.get(current_folder, 0) + 1
            elif os.path.isdir(full_path):
                # 子文件夹压入栈
                stack.append(full_path)
        # 所有子内容都压入后，把当前文件夹的结果存入字典
        result[current_folder] = sub_result.get(current_folder, 0)
    return result

这个优化版的代码，栈里只存文件夹路径，空间占用比之前的版本小很多，而且逻辑也更清晰。

三、递归转非递归的其他坑点

除了顺序和状态标记的坑，递归转非递归还有几个容易踩的坑，需要特别注意。

3.1 坑点3：忽略递归的“返回值”传递

递归的时候，子函数的返回值会自动传递给父函数，但转非递归的时候，需要自己处理返回值的传递。比如刚才的统计文件数量的例子，子文件夹的统计结果需要传递给父文件夹，这就是返回值的传递。

如果忽略了返回值的传递，就会导致父文件夹的统计结果错误。比如刚才的基础版非递归代码，就是因为没有正确传递子文件夹的结果，导致统计错误。

3.2 坑点4：忘记处理“边界条件”

递归的时候，边界条件（比如遍历到文件、遍历到叶子节点）会自动处理，但转非递归的时候，需要自己明确处理边界条件。比如遍历文件夹的时候，遇到文件就直接处理，遇到文件夹就压栈，这就是边界条件的处理。

如果忘记处理边界条件，就会导致栈里压入错误的内容，或者逻辑混乱。比如如果把文件也压入栈，就会导致遍历错误。

3.3 坑点5：过度优化栈空间，导致逻辑复杂

有时候为了优化栈空间，会把栈里的状态拆得太细，导致逻辑变得非常复杂，甚至出现bug。优化栈空间的前提是保证逻辑正确，不能为了优化而牺牲逻辑的清晰性。

比如刚才的优化版代码，栈里只存文件夹路径，逻辑虽然清晰，但如果遇到更复杂的场景，比如需要存更多的状态，就不能过度优化，否则会导致逻辑混乱。

四、应用场景、优缺点及注意事项

4.1 应用场景

递归转非递归主要应用在以下场景：

1. 递归深度超过系统限制：比如遍历嵌套很深的文件夹、处理深度很大的树结构（比如HTML的DOM树、文件系统、目录树）。
2. 栈空间优化：比如在内存有限的设备上运行程序（比如嵌入式设备、移动设备），需要减少栈的空间占用。
3. 性能要求高：非递归版的程序通常比递归版的程序性能更好，因为递归会有函数调用的开销（比如栈帧的创建和销毁）。

4.2 技术优缺点

递归版的优缺点

优点：逻辑简单，代码易读易写，不容易出错。 缺点：递归深度受系统限制，容易栈溢出；有函数调用的开销，性能相对较低；栈空间占用大。

非递归版的优缺点

优点：递归深度不受系统限制，不容易栈溢出；没有函数调用的开销，性能相对较高；可以优化栈空间，减少内存占用。 缺点：逻辑相对复杂，代码难写难读，容易踩坑（比如顺序、状态标记、返回值传递等）。

4.3 注意事项

1. 优先考虑递归：如果递归深度不大，优先使用递归版，因为逻辑简单，不容易出错。
2. 转非递归时先保证逻辑正确：转非递归的时候，先保证逻辑正确，再考虑优化栈空间。
3. 明确状态标记：转非递归的时候，一定要明确状态标记，避免逻辑混乱。
4. 测试遍历顺序：转非递归的时候，一定要测试遍历顺序是否和递归版一致。
5. 合理优化栈空间：优化栈空间的时候，要保证逻辑清晰，不能过度优化。

五、文章总结

递归转非递归是DFS中非常重要的技术，核心是自己模拟系统栈的压栈和弹栈操作。转非递归的时候，容易踩的坑包括栈的顺序搞反、状态标记缺失、忽略返回值传递、忘记处理边界条件、过度优化栈空间等。

递归转非递归的应用场景主要包括递归深度超过系统限制、栈空间优化、性能要求高等。递归版和非递归版各有优缺点，需要根据具体场景选择合适的实现方式。

在实际开发中，如果递归深度不大，优先使用递归版；如果递归深度超过系统限制，或者需要优化栈空间、提高性能，再考虑转非递归版。转非递归的时候，一定要先保证逻辑正确，再考虑优化，避免踩坑。