Recursion with an Array; can't get the right value to return

Question

Solution found - in under 5 minutes, thanks folks!

Clarification: The contents of my array are the values 0-29. So array[0][0] = 0, while array[29][0] = 29 --- they're just test values. Also, I have a potential solution that's been posted multiple times, going to try that.

Recursive Solution: Not working! Explanation: An integer, time, is passed into the function. It's then used to provide an end to the FOR statement (counter<time). The IF section (time == 0) provides a base case where the recursion should terminate, returning 0. The ELSE section is where the recursive call occurs: total is a private variable defined in the header file, elsewhere. It's initialized to 0 in a constructor, elsewhere. The function calls itself, recursively, adding productsAndSales[time-1][0] to total, again, and again, until the base call. Then the total is returned, and printed out later. Well, that's what I hoped for anyway.

What I imagined would happen is that I would add up all the values in this one column of the array and the value would get returned, and printed out. Instead if returns 0. If I set the IF section to "return 1", I noticed that it returns powers of 2, for whatever value time is. EG: Time = 3, it returns 2*2 + 1. If time = 5, it returns 2*2*2*2 + 1.

I don't understand why it's not returning the value I'm expecting. One thing I thought of is that I'm attempting to use private variable total in the return section, along with the recursive call...maybe that's a no-no somehow?

int CompanySales::calcTotals( int time )
{
  cout << setw( 4 );
  if ( time == 0 )
   {
    return 0;
   }
  else
   {
    return total += calcTotals( productsAndSales[ time-1 ][ 0 ]);
   }
}

Iterative Solution: Working! Explanation: An integer, time, is passed into the function. It's then used to provide an end to the FOR statement (counter<time). The FOR statement cycles through an array, adding all of the values in one column together. The value is then returned (and elsewhere in the program, printed out). Works perfectly.

int CompanySales::calcTotals( int time )
{
 int total = 0;
 cout << setw( 4 );

 for ( int counter = 0; counter < time; counter++ )
 {
  total += productsAndSales[counter][0];
 }
 return total0;
}

Answer 1

Well, in your recursive function you're expecting time as a parameter to your function, but when you make the recursive call, its passing the value of your productsAndSales array, not the (time - 1) that I would have expected.

So assuming that the contents of your productAndSales array does not contain zero, the time == 0 termination check will never occur

Answer 2

Should be

return total += productsAndSales[time - 1][0] + calcTotals(time - 1);

Answer 3

Don't use the global total, make it an argument.

int totals = calcTotals(time-1, 0); // Call it starting at the end, 
                                    // so we don't have to pass along the `time`


int CompanySales::calcTotals( int counter, int total )
{
  if ( counter == 0 ) {
    return total;
  }
  else {
    return calcTotals(counter - 1, total + productsAndSales[counter][ 0 ]);
  }
}

Now it's tail recursive too.

Answer 4

Nowhere in your recursive solution are you actually adding a productsAndSales value -- you are passing in those values as the time parameter to your calcTotals() function.

So if total starts as zero, you are simply calling this function a number of times and never adding anything other than zero to it.

Answer 5

Wrong argument being passed around:

total += calcTotals( productsAndSales[ time-1 ][ 0 ]);

Should be:

total +=  productsAndSales[ time ][ 0 ]  + calcTotals(time - 1);

Answer 6

Shouldn't this be

int CompanySales::calcTotals( int time )
{
  int total = 0;
  cout << setw( 4 );
  if ( time == 0 )
   {
    return 0;
   }
  else
   {
    return total += productsAndSales[ time ][ 0 ] + calcTotals( time - 1);
   }
}

Answer 7

This should produce the same result as the iterative function.

int CompanySales::calcTotals( int time )
{
  cout << setw( 4 );
  if ( time == 0 ){
    return 0;
  }
  else{
    return productsAndSales[time-1][ 0 ] + calcTotals( time - 1 );
  }
}