C语言不修改test函数声明前提下加速三阶递推递归函数的方法

原函数性能差的核心原因是存在大量重复子问题计算，时间复杂度为指数级O(3ⁿ)，n增大时调用次数呈爆炸式增长。在不修改函数声明的前提下，有两种常用的高效实现方案：

方案1：迭代实现（最优，无额外空间开销） #

直接从底向上递推，仅保留最近3个计算结果，时间复杂度O(n)，空间复杂度O(1)，完全消除递归栈开销和重复计算。
代码示例：

int test(int n) {
    // 边界条件和原逻辑完全一致
    if (n <= 2) {
        return n;
    }
    // 分别存储f(n-3)、f(n-2)、f(n-1)的结果
    int t0 = 0, t1 = 1, t2 = 2, cur;
    for (int i = 3; i <= n; i++) {
        cur = t0 + t1 + t2;
        // 滚动更新三个前置值
        t0 = t1;
        t1 = t2;
        t2 = cur;
    }
    return cur;
}

方案2：记忆化递归（改动最小，保留递归写法） #

用静态缓存存储已经计算过的结果，避免重复计算，时间复杂度O(n)，空间复杂度O(n)，适合不想修改原有递归逻辑的场景。
代码示例：

int test(int n) {
    // 静态缓存：int类型下三阶递推到n=36就会溢出，开50长度足够覆盖所有有效输入
    static int cache[50];
    // 首次调用初始化缓存标记，-1表示未计算
    static int cache_init = 0;
    if (!cache_init) {
        for (int i = 0; i < 50; i++) {
            cache[i] = -1;
        }
        cache[0] = 0;
        cache[1] = 1;
        cache[2] = 2;
        cache_init = 1;
    }
    // 非法输入兼容
    if (n < 0 || n >= 50) {
        return 0;
    }
    // 缓存命中直接返回
    if (cache[n] != -1) {
        return cache[n];
    }
    // 未命中则计算并存入缓存
    cache[n] = test(n-1) + test(n-2) + test(n-3);
    return cache[n];
}

如果需要处理n极大的场景（超过int溢出范围，搭配大整数实现），可以进一步用矩阵快速幂把时间复杂度降到O(logn)，普通场景下前两种方案已经足够满足性能需求。

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