1

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;
}
5
  • 2
    What's with the random setw in the functions? You aren't printing anything. Also, there is no total in the recursive function. Is that global?
    – GManNickG
    Mar 16, 2010 at 16:48
  • It'd be helpful if you posted the contents of your productsAndSales array. Mar 16, 2010 at 16:49
  • Indeed, unless I'm mistaken you're passing the wrong thing into your recursive call. Mar 16, 2010 at 16:50
  • @Gman, sorry, I thought about taking the setw since it's just garbage to you folks - it's part of my formatting as it were. Still, should've taken taken it out just for the code example here.
    – Azoreo
    Mar 16, 2010 at 17:01
  • @overslacked - posted them, but they're just test values @Ron - Well, yes and no, I didn't really write the call in an effective fashion.
    – Azoreo
    Mar 16, 2010 at 17:02

7 Answers 7

6

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.

2
  • Damn, I was kinda thinking that was it...let me try that
    – Azoreo
    Mar 16, 2010 at 16:55
  • GAH. Perfect solution. I had realized I should be passing total as an argument rather than using the global version, but I would've never figured out the way to write the recursive call as well as you did - thanks.
    – Azoreo
    Mar 16, 2010 at 17:00
3

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

1
  • @Steve - well, this was mostly just an initial test for the recursive function. I should have (and have now) posted the contents of my array, which are just (non-zero) test values.
    – Azoreo
    Mar 16, 2010 at 17:03
2

Wrong argument being passed around:

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

Should be:

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

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 );
  }
}
1
  • Works, you're the third to post it ;0 Wish I had thought of it.
    – Azoreo
    Mar 16, 2010 at 17:06
1

Should be

return total += productsAndSales[time - 1][0] + calcTotals(time - 1);
1
  • This works as well I believe - didn't test, but looks like a similar answer which worked.
    – Azoreo
    Mar 16, 2010 at 17:06
0

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.

2
  • They were non-zero values (posted them).
    – Azoreo
    Mar 16, 2010 at 17:06
  • Right, but you never actually added them -- they were always parameters to another invocation of the calcTotals() function. Eventually you'd get to the point where the time value was zero and then that zero value would percolate back up. Glad you found a good answer above, though!
    – mwigdahl
    Mar 16, 2010 at 17:14
0

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);
   }
}
3
  • I don't think so - each time you call it, recursively, it'll be setting total to 0.
    – Azoreo
    Mar 16, 2010 at 17:05
  • No, it won't as the variables are created on a stack with different scope for each call. However the size of the stack may restrict your ability to recurse indefinitely.
    – questzen
    Mar 16, 2010 at 17:26
  • On a different note, your assumption that the state of the variables would persist across calls, leads to a different programming construct called "closures".
    – questzen
    Mar 16, 2010 at 17:30

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.