Почему эта некорректная запомненная функция Фибоначчи работает?

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]".