error C2106: '=' : left operand must be l-value in Fibonacci sequence by dynamic programming in C++

Question

I am trying to write a program for generating Fibonacci sequence by dynamic programming approach as follows.

#include<iostream>
#include<ctime>

int fib(int index)
{
    int memo[] = {0};
    memo[0] = 0;
    memo[1] = 1;
    for(int i = 2; i <= index; i++)
    {
        fib(index) = fib(index - 1) + fib(index - 2);   //error comes here
    }
    return fib(index);
}
int main()
{   
    time_t start, end, diff;
    int index;
    std::cout << "Please, enter the index of fibonacci sequence" << std::endl;
    std::cin >> index;
    start = time(NULL);
    std::cout << "calculating...." << std::endl << fib(index) <<std::endl;
    end = time(NULL);
    diff = (time_t)difftime(end, start);
    std::cout << "Time elapsed: " << diff << std::endl;
    return 0;
}

But, in the line fib(index) = fib(index - 1) + fib(index - 2); Iam getting error as

error C2106: '=' : left operand must be l-value

So, please tell me what's wrong I have done in that line. Thanks in advance.

Answer 1

You're assigning to an l-value (which is what int fib(int) returns). Just like the error message states.

Also note that int memo[] = {0}; creates an array of size 1, so writing beyond index 0 is invalid.

Answer 2

You can't assign to fib(index) as others pointed out already. There is workaround by returning reference or pointer.

But the program itself is wrong as it goes into infinite loop. The line

fib(index) = fib(index - 1) + fib(index - 2);  

Keeps launching fib(index) if index > 1. The correct way of solving Fibonacci using DP is

int fib(int n)
{
  int a = 0, b = 1, c, i;
  if( n == 0)
    return a;
  for (i = 2; i <= n; i++)
  {
     c = a + b;
     a = b;
     b = c;
  }
  return b;
}

Answer 3

You must introduce a temporary variable like this:

int result = 0;
for(int i = 2; i <= index; i++)
{
    result = fib(index - 1) + fib(index - 2);   //error comes here
}
return result;

But this is just the technical solution. As Bala pointed out, your algorithm as such does not work.

This could be a solution, if you are looking for a recursive one:

int fib(int index)
{
    switch(index) {
    case 0:
        return 0;
    case 1:
        return 1;
    default:
        return fib(index - 1) + fib(index -1);
    }
}

For a true dynamic solution you would store all calculated values into a static memo and reuse if it already exists.

int fib(int index)
{
    // Stores fib for given index
    static std::map<int, int> memo;

    if (index == 0) return 0;
    else if (index == 1) return 1;
    else {
       auto it = memo.find(index);
       if (it == memo.end()) {
           int r = fib(index - 1) + fib(index -2);
           memo[index] = r;
       } else return *it;
    }
}