一、递归思想：从文件目录树说起

说实话，递归这个概念，很多初学者都觉得玄乎。我当年学的时候也一样——明明一个循环就能搞定的事，干嘛非要自己调用自己？直到我在实际项目中遇到了文件目录遍历，才真正体会到递归的威力。

你想想看，一个文件目录长什么样？根目录下面有子目录，子目录下面还有子目录，子子目录下面可能还有文件。这种结构，用数学术语叫「树形结构」。而处理树形结构，递归几乎是天然的选择。

二、目录树的数学模型

我们先给目录树建个模。一个目录节点，要么是文件（叶子节点），要么是目录（非叶子节点）。目录下面可以挂文件，也可以挂子目录。

用C语言的结构体来表示，大概长这样：

// 文件/目录节点
typedef struct TreeNode {
    char name[256];          // 文件名或目录名
    int is_dir;              // 1表示目录，0表示文件
    struct TreeNode *first_child;  // 第一个子节点
    struct TreeNode *next_sibling; // 下一个兄弟节点
} TreeNode;

这种结构叫「孩子兄弟表示法」。每个节点有两个指针：一个指向第一个孩子，一个指向下一个兄弟。说白了，就是用二叉树的方式来表示多叉树。

我刚开始做这个设计时，其实纠结过要不要用动态数组来存子节点。后来发现，用链表的方式更灵活，插入删除都方便，而且递归遍历时逻辑特别清晰。

三、递归遍历的核心逻辑

遍历一棵目录树，我们需要做什么？

1. 访问当前节点（打印名字）
2. 如果是目录，就遍历它的所有子节点
3. 对每个子节点，重复步骤1和2

你看，这不就是递归吗？

void traverse_tree(TreeNode *node, int depth) {
    if (node == NULL) return;

    // 打印当前节点，缩进表示层级
    for (int i = 0; i < depth; i++) {
        printf("  ");
    }
    if (node->is_dir) {
        printf("[DIR] %s\n", node->name);
    } else {
        printf("[FILE] %s\n", node->name);
    }

    // 如果是目录，递归遍历子节点
    if (node->is_dir) {
        TreeNode *child = node->first_child;
        while (child != NULL) {
            traverse_tree(child, depth + 1);
            child = child->next_sibling;
        }
    }
}

这段代码，核心就两件事：打印自己，然后让每个孩子重复做同样的事。depth参数用来控制缩进，这样打印出来就能看到层级关系。

四、构建一棵示例目录树

光说不练假把式。我们来手动构建一棵目录树，然后遍历它。

// 创建一个新节点
TreeNode* create_node(const char *name, int is_dir) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    strcpy(node->name, name);
    node->is_dir = is_dir;
    node->first_child = NULL;
    node->next_sibling = NULL;
    return node;
}

// 添加子节点
void add_child(TreeNode *parent, TreeNode *child) {
    child->next_sibling = parent->first_child;
    parent->first_child = child;
}

int main() {
    // 构建目录结构：
    // root/
    //   ├── usr/
    //   │   ├── bin/
    //   │   │   └── gcc
    //   │   └── lib/
    //   │       └── libc.so
    //   └── home/
    //       └── user1/
    //           └── readme.txt

    TreeNode *root = create_node("root", 1);
    TreeNode *usr = create_node("usr", 1);
    TreeNode *home = create_node("home", 1);
    TreeNode *bin = create_node("bin", 1);
    TreeNode *lib = create_node("lib", 1);
    TreeNode *user1 = create_node("user1", 1);
    TreeNode *gcc = create_node("gcc", 0);
    TreeNode *libc = create_node("libc.so", 0);
    TreeNode *readme = create_node("readme.txt", 0);

    add_child(root, home);
    add_child(root, usr);
    add_child(usr, lib);
    add_child(usr, bin);
    add_child(bin, gcc);
    add_child(lib, libc);
    add_child(home, user1);
    add_child(user1, readme);

    printf("目录树遍历结果：\n");
    traverse_tree(root, 0);

    // 释放内存（略）
    return 0;
}

运行结果：

目录树遍历结果：
[DIR] root
  [DIR] home
    [DIR] user1
      [FILE] readme.txt
  [DIR] usr
    [DIR] lib
      [FILE] libc.so
    [DIR] bin
      [FILE] gcc

嗯，层级关系一目了然。注意看，home和usr是兄弟节点，它们都在root下面。而bin和lib是usr的子节点，所以缩进更深。

五、递归的深度与栈溢出

说到递归，就不得不提栈溢出。我曾经在一个嵌入式项目里吃过这个亏——目录嵌套了100多层，递归直接爆栈了。

怎么估算栈空间？每个递归调用大概占用几十到几百字节（取决于局部变量多少）。Linux默认栈大小是8MB，算下来大概能支持几万层递归。但Windows默认只有1MB，所以更危险。

我的建议是：如果目录深度可能超过500层，就别用递归了。或者至少加一个深度计数器，超过阈值就报错退出。

六、知识体系总览

下面这张图，把本章的核心知识点串起来了：

七、避坑指南与经验总结

最后，分享几个我踩过的坑：

• 忘记处理空指针——递归函数进来第一件事就是判断node是否为NULL。我曾经漏掉这个检查，结果遍历到叶子节点时直接段错误。
• 递归深度没控制——前面说过了，超过一定深度就要考虑迭代方案。我建议在递归函数里加一个static计数器，超过阈值就打印警告。
• 内存泄漏——构建的树别忘了释放。每个malloc都要对应一个free，最好写一个递归的free_tree函数。
• 打印格式混乱——用depth控制缩进时，注意depth从0开始还是从1开始。我个人习惯根节点depth=0，这样缩进正好对应层级。

嗯，递归遍历目录树，说白了就是「走一步，看一步，遇到目录就钻进去」。掌握了这个思想，后面处理JSON解析、表达式求值、甚至游戏里的场景图遍历，都会轻松很多。