c - 为什么这个不正确的内存斐波那契函数有效？

Question

这是内存斐波那契的错误实现:

long int fib(int n) {
    long int memo[100];
    if(n<2) {
        return n;
    }
    if(memo[n] != 0) {
        return memo[n];
    }
    else {
        memo[n] = fib(n - 1) + fib(n - 2);
        return memo[n];
    }
}

这是不正确的，因为数组 memo 每次调用都是一个全新的数组，并且没有发生内存。最简单的解决方法是制作memo static。但是，你瞧，代码有效!

我在调试器中单步执行它，memo 的行为就好像它是静态的一样!看起来编译器生成的代码在每次调用时将 memo 放在相同的内存空间中，而不是新的新鲜内存。这是为什么？

使用的编译器是 Apple clang 版本 11.0.0 (clang-1100.0.33.12)。

Answer 1

它是 UB，但如果我们假设新线程的堆栈仅包含零， 那么 memo[100] 中的所有值都可以是零或先前调用该函数的保留值。

有效的算法可能如下所示:

long int memo[100] = {0};

long int fib(int n) {
    if(n<2) {
        return n;
    }
    if(memo[n] != 0) {
        return memo[n];
    }
    else {
        memo[n] = fib(n - 1) + fib(n - 2);
        return memo[n];
    }
}

除了递归的每一层都有自己的'memo[100]'。