1

I recently read about memoization for the first time(I'm a noob) and I wanted to try and make a fibonacci function that uses memoization. This is what I've tried, but anything over 1 just gives me a segmentation fault. Any help is appreciated! 

unsigned int fibonacci( unsigned int n )
{
    vector<unsigned int> fibvector;
    if ( n <= 1 )
        return n;
    if ( fibvector.size() >= n )
        return fibvector[n];
    unsigned int add = fibonacci( n-1 ) + fibonacci( n-2 );
    fibvector[n] = add;
    return add;
}
Improve this question
3
  • 2
    You haven't allocated memory for the vector but you're using [n] to access its contents. Commented Jun 23, 2013 at 12:43
  • How do I do this manually? I thought the vector would allocate the memory itself? Commented Jun 23, 2013 at 12:46
  • 1
    It does, but only when you do something like push_back(n). When you use [n], it returns a reference to a memory address that it hasn't allocated space for internally. Only after you use push_back can you do that. Commented Jun 23, 2013 at 12:49

2 Answers 2

Reset to default
6 
vector<unsigned int> fibvector;

is a local variable. each time you call fibonacci(n) there will be a new vector created, with no elements. You can fix it by making it static.

static vector<unsigned int> fibvector(MAXELEMENTS);

MAXELEMENTS is used for initialization purposes. And in this case, you need to test using 

if(fibvector[n] != 0) return fibvector[n];

Edit: If you want to not require a fixed amount of elements you can use the following

unsigned int fibonacci( unsigned int n )
{
    static vector<unsigned int> fibvector;
    unsigned int fib;

    if ( fibvector.size() > n )
        return fibvector[n];
    if(n <=1){
       fib = n;
    }
    else{
       unsigned int v2 = fibonacci( n-2 );
       unsigned int v1 = fibonacci( n-1 );
       fib = v2 + v1;
    }
    fibvector.push_back(fib);
    return fib;
}

The idea is that the recursion method of fibonacci(n) would first compute fibonacci(0), fibonacci(1), fibonacci(2) till fibonacci(n). Which means it will compute following the natural order of n, and the push_back will accurately follow this ordering.

Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

I'd make this vector a reference parameter to the function rather declaring it static.
Thanks a lot! But do you have to set the maxelements in the beginning? I would like it to ideally have no max elements.
@Arnstein: Yes, you may, but then you have to make sure to regrow it whenever it is too small. I'd recommend making the vector a reference parameter, as g-makulik suggests. You can even overload your function in order to provide a clean interface (that is, fibonacci(n), would call fibonacci(n,vector<unsigned int>(n))).
@UmNyobe This code give me the wrong numbers.{ static vector<unsigned int> fibvector; unsigned int add = 1; if ( n <= 1 ) return n; if ( fibvector.size() > n ) return fibvector[n]; if ( n > 1 ) { unsigned int v1 = fibonacci( n-2 ); unsigned int v2 = fibonacci( n-1 ); add = v2+v1; } fibvector.push_back( add ); return add; }
if ( n <= 1 ) return n; well this is incorrect Fibonnaci(0)=1, and i didnt mention that. It was one of the bug in your original post. I tested the correctness of the function i posted.
|
0

Others have commented on your lack of push_backs for your vector. I'll add that your vector is purely local to one call of your function--it has no scope up and down the recursive call stack so it won't function as you anticipated. Instead, you need to make the vector static, or better yet pass it by reference to each recursive call. Better still would be to make this a class.

Improve this answer

1 Comment

My goal is to make it a class, I just wanted to try it out in a simple function first!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.