20、指针与递归：递归函数中的指针传递、递归遍历链表、递归遍历二叉树

指针和递归，这两个东西单独拎出来都够喝一壶的。把它们放一起？很多人第一反应是「头大」。但说实话，在嵌入式开发里，这俩是黄金搭档。尤其是处理链表、二叉树这类动态数据结构时，递归配合指针，代码能写得又短又清晰。

我个人习惯是：能用递归解决的问题，绝不硬写循环。当然，前提是递归深度可控。嗯，这里要注意——嵌入式环境里栈空间有限，递归太深容易爆栈。这个我们后面会细说。

递归函数中的指针传递

先聊个基础问题：递归函数里，指针怎么传？

其实很简单——传指针就是传地址。递归调用时，每一层函数都有自己的栈帧，但指针指向的是同一块内存。这意味着你在递归深处修改了数据，外层也能看到。

举个例子，写一个递归函数，把链表里所有节点的值加1：

void increment_all(Node *head) {
    if (head == NULL) return;   // 递归终止条件
    head->value += 1;           // 修改当前节点
    increment_all(head->next);  // 递归处理下一个
}

你看，这里传的是 Node *head，每一层递归都拿着同一个链表的节点指针。修改是「原地」的，不需要返回值。这就是指针传递的威力——递归调用链上的所有函数，共享同一份数据。

递归遍历链表

链表遍历，用循环写很直观。但用递归写，代码更简洁，而且能帮你理解「递归思维」。

先看一个正向遍历的例子：

void print_list(Node *head) {
    if (head == NULL) {
        printf("NULL\n");
        return;
    }
    printf("%d -> ", head->value);
    print_list(head->next);
}

输出：10 -> 20 -> 30 -> NULL

那反向遍历呢？只需要调换一下顺序：

void print_list_reverse(Node *head) {
    if (head == NULL) return;
    print_list_reverse(head->next);
    printf("%d -> ", head->value);
}

输出：30 -> 20 -> 10 -> NULL

为什么会这样？因为递归调用是「先递后归」。正向遍历是在「递」的过程中打印，反向遍历是在「归」的过程中打印。你想想看，这比用栈或者反转链表简单多了吧？

递归遍历二叉树

二叉树才是递归的「主场」。二叉树的天然递归结构——每个节点又是一棵子树的根——让递归遍历变得极其自然。

三种经典遍历方式，用递归写出来几乎就是「教科书」级别的简洁：

// 前序遍历：根 -> 左 -> 右
void preorder(TreeNode *root) {
    if (root == NULL) return;
    printf("%d ", root->value);
    preorder(root->left);
    preorder(root->right);
}

// 中序遍历：左 -> 根 -> 右
void inorder(TreeNode *root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->value);
    inorder(root->right);
}

// 后序遍历：左 -> 右 -> 根
void postorder(TreeNode *root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->value);
}

代码几乎一模一样，只是 printf 的位置不同。这就是递归的美妙之处——逻辑清晰，不易出错。

我记得有一次做嵌入式文件系统，需要遍历目录树来统计文件大小。目录结构本身就是一棵多叉树，我用递归后序遍历，每个子目录的大小由子节点累加得到。代码不到20行，搞定。

递归遍历的核心逻辑

下面这张图，帮你理清递归遍历二叉树的核心逻辑：

说白了，递归遍历就是「遇到节点，决定什么时候处理它」。前序、中序、后序的区别，仅仅是 printf 的位置不同。这个规律记牢了，二叉树遍历你就掌握了八成。

递归遍历的实际应用

光说不练假把式。我举两个实际场景：

场景一：计算二叉树深度

int tree_depth(TreeNode *root) {
    if (root == NULL) return 0;
    int left_depth = tree_depth(root->left);
    int right_depth = tree_depth(root->right);
    return (left_depth > right_depth ? left_depth : right_depth) + 1;
}

这个函数用后序遍历的思想：先算左子树深度，再算右子树深度，取较大值加1。递归的每一层都返回当前子树的深度，最终得到整棵树的高度。

场景二：释放二叉树所有节点

void free_tree(TreeNode *root) {
    if (root == NULL) return;
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

这里必须用后序遍历。为什么？因为你要先释放子节点，再释放父节点。如果先释放父节点，子节点就找不到了——内存泄漏的坑就是这么来的。

递归 vs 循环：怎么选？

我列个对比表，帮你快速决策：

对比维度	递归	循环
代码简洁度	极高，尤其适合树形结构	一般，需要手动维护栈
可读性	逻辑清晰，接近数学定义	需要理解循环控制流
栈空间	每层递归消耗栈帧	只消耗一层栈帧
适用场景	深度可控的树/链表遍历	深度大、性能敏感的场景
嵌入式建议	深度 < 100 层可用	深度不限，推荐使用

我个人习惯是：二叉树遍历无脑用递归。链表遍历看情况——链表短（几十个节点）用递归，链表长（几百上千）用循环。毕竟嵌入式环境里，栈空间是稀缺资源，不能乱来。

小结

指针和递归的组合，说白了就是「用指针共享数据，用递归简化逻辑」。链表和二叉树的递归遍历，是理解这个组合的最佳练习。你只要记住三点：

• 递归终止条件必须写，而且必须写在最前面
• 指针传递让所有递归层共享同一份数据
• 前序、中序、后序的区别，就是处理节点的时机不同

把这些练熟了，指针和递归这块你就拿下了。后面遇到更复杂的数据结构，比如红黑树、AVL树，递归遍历的思路完全一样，只是处理逻辑更复杂一些。

---