如何优化C语言递归函数？递归计数函数性能优化咨询

一、速度差异的原因 #

核心问题出在全局静态变量remaining上：

• 内存访问开销极高：全局变量存储在进程数据段，不属于CPU高速缓存的热点区域，每次递归中的remaining++都要访问主存，而主存访问延迟是寄存器/栈缓存的几十倍。相比之下，printf虽涉及IO，但标准库默认开启输出缓冲，大部分输出先写入用户态缓冲区，实际触发的系统调用极少，用户态内存操作开销被大幅摊薄，整体反而比频繁读写全局变量更快。
• 编译器优化受限：全局变量的存在让编译器无法将计数操作放入寄存器优化（即使没有多线程，编译器也会做保守假设，认为全局变量可能被外部修改），而printf作为成熟库函数，编译器可对其调用做批量优化，或因IO操作的特性掩盖了部分开销。

另外原函数还存在功能bug：多次调用Unmarked_Nodes时，remaining不会自动重置，会返回错误的累积值。

二、Unmarked_Nodes的优化方案 #

1. 移除全局变量，改用递归返回计数（最优方案） #

将计数逻辑改为递归函数返回当前子树的未标记节点数，所有操作在栈或寄存器中完成，彻底避免全局内存访问：

int Unmarked_Nodes(tree root) {
    if (root == NULL) {
        return 0;
    }
    int left_count = Unmarked_Nodes(root->left);
    int right_count = Unmarked_Nodes(root->right);
    return left_count + right_count + (root->marker == 0 ? 1 : 0);
}

该方案优势：

• 数据操作均在栈帧/寄存器中，缓存命中率极高，速度远快于全局变量版本。
• 函数可重入，多次调用不会出现结果错误。
• 编译器可对其充分优化（如-O2级别下会将变量放入寄存器、做递归展开等）。

2. 改用迭代遍历（避免递归栈溢出） #

如果树的深度极大，递归可能触发栈溢出，此时可用栈模拟中序遍历：

#include <stdlib.h>

int Unmarked_Nodes(tree root) {
    if (root == NULL) {
        return 0;
    }
    int count = 0;
    // 可根据树深调整栈大小，或实现动态扩容
    tree* stack = malloc(sizeof(tree) * 1024);
    int top = 0;
    tree current = root;

    while (current != NULL || top > 0) {
        // 遍历所有左子节点
        while (current != NULL) {
            stack[top++] = current;
            current = current->left;
        }
        current = stack[--top];
        // 统计当前节点
        if (current->marker == 0) {
            count++;
        }
        // 转向右子树
        current = current->right;
    }
    free(stack);
    return count;
}

该方案避免了递归调用的栈开销，适合超大型树的场景。

3. 开启编译器优化选项 #

编译时添加-O2或-O3选项，编译器会自动完成寄存器分配、循环展开、冗余操作消除等优化，进一步提升运行速度。

内容的提问来源于stack exchange，提问作者user19617564