CODEWITHSUNDEEP
crecursionfibonacci
screwnut
screwnut

Reputation: 1383

Why does this incorrect memoized fibonacci function work?

Here's an incorrect implementation of memoized fibonacci:

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];
    }
}

It is incorrect because the array memo is a brand new array each call and no memoization is occuring. The easiest fix is to make memo static. But, lo and behold, the code works!

I stepped through it in the debugger and memo is behaving as if it was static! It appears that the compiler generated code that is placing memo in the same memory space at every call as opposed to new fresh memory. Why is that?

Compiler used is Apple clang version 11.0.0 (clang-1100.0.33.12).

Upvotes: 1

Views: 70

Answers (1)

SKi
SKi

Reputation: 8466

It is UB, but if we assume that stack of a fresh thread contains only zeroes, then all values in memo[100] can be zeroes or remains of previous call of the function.

The effective algorithm might work like the following:

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];
    }
}

Except each layer of recursion have own 'memo[100]'.

Upvotes: 1

Related Questions