Why does this code print rubbish?

Question

This is a simple recursive method with caching so that the numbers will not get recalculated over and over again. I've definitely seen it work, but now it's broken and prints rubbish. I've tried reverting to working version, but just can't find any difference that could have broken it.

Why did it stop working?

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int Fibonacci_vector(int n) {
    static vector<int> cache(2, 1);
    cache.reserve(n);
    if (cache[n] == 0) {
        cache[n] = Fibonacci_vector(n-1) + Fibonacci_vector(n-2);
    }
    return cache[n];
}

int main() {
    cout << Fibonacci_vector(4);
}

UPDATE Jeez, I'm so stupid that it just hurts. I've changed if (n > cache.size()) { cache.resize(n); } to cache.reserve(n); and of course it broke everything! So sorry for my stupidity, guys.

This doesn't compile. You're trying to access memory in which you don't have access to. — Tarik Neaj, Jan 13 '16 at 20:52
@TarikNeaj, [It compiles.](http://coliru.stacked-crooked.com/a/1b414ac0c96aec67) — chris, Jan 13 '16 at 20:52
you also recursve infinitely, since you never check if `n` goes below 1, you'll eventually be calling `Fibonacci_vector(-99999999)` — Marc B, Jan 13 '16 at 20:54

score 5 · Accepted Answer · edited Jun 20 '20 at 09:12

There's std::vector::reserve and there's also std::vector::resize. They do different things.

^{cache[n] is still access out of range in both cases (one past last element in case of std::vector::resize)}
The condition for calculation should not try to access any cached data (out of range), it just has to compare if(n >= cache.size()).
You'll need to call cache.resize(n + 1) only if the condition above is satisfied, so put it inside the if-clause.

SashaMN · Answer 2 · 2016-01-13T20:58:25.770

1

You need to check that the element exists. Change the code like this:

int Fibonacci_vector(int n) {
    static vector<int> cache(2, 1);
    if (n >= cache.size()) {
        cache.push_back(Fibonacci_vector(n-1) + Fibonacci_vector(n-2));
    }
    return cache[n];
}

edited Jan 13 '16 at 20:58

answered Jan 13 '16 at 20:53

SashaMN

708
5
16

Why does this code print rubbish?

2 Answers2