memoization for fibonacci array

[funprogrammer]

Can someone tell me how I could do this in c++. I can't use the same array which I am updating. In other words, if I uncomment the commented line I get an error.

#include <iostream>
#include <vector>
using namespace std;
vector<int> fib(int n){
  vector<int> res;
  for(int i=0;i<n;i++){
  	//res.push_back(n<2?1:res[n-1]+res[n-2]);
  	res.push_back(n<2?1:2);
  }
  return res;
}
int main() {
	// your code goes here
	int n;
	cout<<"enter number"<<endl;
	cin>>n;
	vector<int> test = fib(n);
	cout<<"test size is "<<test.size()<<endl;
	for(auto a :test){
		cout<<a<<" ";
	}
	cout<<endl;
	return 0;
}

[ne555]

> I get an error.
otherwise you wouldn't be here, you need to be more descriptive.

> res.push_back(n<2?1:res[n-1]+res[n-2]);
¿what's the value of `n' on the first iteration? ¿how many elements does `res' hold then?
¿what's the value of `n' on the second iteration?, ¿the third?, ¿the last one?

[funprogrammer]

The program outputs when the input is 1, anything more than 1(2 or more) the program terminates with "Exit Code: 0(normal program termination)" and there is no output.
I was thinking it maybe related to trying to write while I am trying to read from it is causing an error. Please advise what may be going on here.

[JLBorges]

#include <vector>
#include <limits>

bool push_next( std::vector<int>& fib_seq ) // append the next term 
{
    const auto sz = fib_seq.size() ;

    // classical fibonacci sequence starts with { 1, 1 }
    if( sz < 2 ) fib_seq.push_back(1) ;

    else // sz >= 2
    {
        const unsigned long long prev = fib_seq.back() ;
        const auto next = prev + fib_seq[sz-2] ; // next term in the fibonacci sequence

        if( next > std::numeric_limits<int>::max() ) return false ; // overflow
        else fib_seq.push_back(next) ;
    }

    return true ;
}

std::vector<int> fib( std::size_t n ) // the first 'n' fibonacci numbers
{
    std::vector<int> seq ;
    while( seq.size() < n && push_next(seq) ) ;
    return seq ;
}

http://coliru.stacked-crooked.com/a/aacd879bf8e9acab

[mbozzi]

Here is a recursive definition for the nth fibonacci term:

int fibonacci(std::size_t n) { 
  return (n < 2)? n: (fibonacci(n - 1) + fibonacci(n - 2));
}

Makes sense, hopefully?
The problem with this naive approach is that looking for the fourth term (fibonacci(4)), requires 5 calls to fibonacci(), a hell of a lot just to get 3 as the answer. Your computer is fast, but not that fast. You'll probably start feeling a delay around term 35; once you try for fibonacci(100), you'll be there for a Very Long Time waiting for all 708,449,696,358,523,830,148 recursive invocations to complete.

Line 5:
The vector is local to the function, which means that each recursive call gets its' own vector. Move it outside the function, or pass a reference to a vector into the function.
Line 7:
This is correct -- but line 8 isn't.

Each iteration, check to see if the value you are computing is in the vector. If it is, then simply return that. If it isn't, compute it, add it, and return the computed value.
The key point is that each function call needs access to the same vector.

[ne555]

> I was thinking it maybe related to trying to write while I am trying to read
> from it is causing an error.
The problem is that you are trying to access your vector out of bounds.
If you try to answer my questions you may realize it.

[lastchance]

Line 7:
This is correct -- but line 8 isn't. 

Line 7 isn't correct: use i, not n (all three times)

I suspect a vector would be a lot more expensive than a normal (but dynamically allocated) integer array.

[keskiverto]

I suspect a vector would be a lot more expensive than a normal (but dynamically allocated) integer array.

Why?

We do know that we will push (at most) n elements to the vector.
It is easy to res.reserve( n ); before the loop.

[funprogrammer]

@ne555: got it, I was stupid, it should be i instead of n. It works after changing it.

Thanks for all the input guys.