Code runs but shows no output after inputting a value

Question

I'm trying to implement dp on a fibonacci sequence using vector.If i declare memo globally as an array with given size it runs fine.But while using vector it shows no output on the console. What seems to be the problem here?

#include<bits/stdc++.h>
using namespace std;
int fib(int n)
{
    vector<int>memo;
    int f;
    if(memo[n]!=0)
        return memo[n];
    if(n<=2)
        return 1;
    else
        f = fib(n-1)+fib(n-2);
    memo.push_back(f);
    return f;

}

int main()
{
    int num;
    cin>>num;
    cout<<fib(num);
}

Answer 1

The problem here is your declaration of memo:

vector<int>memo;

It is not static, and thus goes out of scope every time the function exits. However, you seem to expect it to still be in scope when the function exits.

Thus, make it static:

static vector<int>memo;

---

Side note: I would check that n is less than memo.size() before trying to do something like if(memo[n]!=0), because if n is greater than the size, then I believe this is undefined behavior.

Side note 2: You shouldn't include bits/stdC++.h

Answer 2

Here's the corrected code.

#include <iostream>
#include <vector>

using namespace std;

int fib (int n)
{
    static vector<int>memo = {1, 1}; // should be static. also init it.
    int f;
    if (n < memo.size () && memo [n] != 0) // check the size of vector before accessing
        return memo [n];
    if (n <= 2)
        return 1;
    else
        f = fib (n - 2) + fib (n - 1); // n-2 should be found and inserted before n-1
    memo.push_back (f);
    return f;

}

int main ()
{
    int num;
    cin >> num;
    cout << fib (num);
}

There were three main issues with the code.

• memo should have been declared as static. Previously with each call to fib(), it was creating a fresh 'memo' variable.

• memo[n]!=0 might cause a segfault since the vector could be small. You should check the size before referencing nth item.

• You were pushing the n'th value to (n-2)'th place. So let's first initialize the vector with {1,1}

Now the series will be generated as... 1 1 2 5 8 13 21 34 55

Answer 3

There are some problems in your code:

1. You are not allocating space on memo and this is why you get no output.
2. memo must be static so it lives over the recursion and you can get real memoization
3. You are using memo.push_back(f);. This defeats memoization because the indices will not correspond to what you want to find in memo

Fixing these issues leads to a code like this:

#include<iostream>
#include<vector>
using namespace std;
int fib(int n)
{
    static vector<int> memo(n + 1, 0);
    if (n > memo.capacity() - 1)  
        memo.resize(n + 1, 0);

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

}

int main()
{
    int num;
    cin >> num;
    cout << fib(num) << endl;
}

Answer 4

1. The reason nothing is shoring it is the program is running, but you don't know. Change to this it will show.

   cout << "Enter a number : "; cin >> num;

2. because you are using recursive, in the fib() function, you create memo multiple times. This will return "program terminated with signal 11 segmentation fault"

3. When you first call fib(), there's nothing in the memo, so you cannot do memo[n].

Hope this helps.

Answer 5

I figured it out.

I changed the checking statement if(memo[n]!=0) to this if(!memo.empty()). And the rest are all the same.

Answer 6

This approach - recursion with memoization - is much easier with a map:

#include <iostream>
#include <map>
using namespace std;

int fib(int n) {
    static map<int, int> memo;     #pairs are n, f
    int f = 0;
    if (memo.count(n) > 0)
        return memo.at(n);
    if (n <= 2 )
        return 1;
    else 
        f = fib(n - 1) + fib(n - 2); 
    memo.emplace(n, f);
//  cout << n << " " << f << endl;   #run this with and w/o 'static' to see effect
    return f; 
}

int main() {
    for (int i = 1, i < 12, i++)
        cout << fib(i) << " ";
    cout << endl;
}

gives:

1 1 2 3 5 8 13 21 34 55 89

[Edit] : Here's the vector version, it needed this loop inside however:

int fibVec(int n) {
    static vector<int> memo;
    int f = 0;
    for (int i = 0; i < memo.size(); i++) {  //search the vector by index
        if (i == n) 
            return memo[i];
    }
    if (n <= 2 )
        return 1;
    else 
        f = fib(n - 1) + fib(n - 2); 
    memo.push_back(f);
    return f; 
}