We're a community of 1.1M IT Pros here for help, advice, solutions, professional growth and fun. Join us!
1,080,594 Members — Technology Publication meets Social Media

# Recursive reduce

HI I would like to modify the following function so that it could take any of the operators such as +,-,* or /. I want to know if its possible to do this without having to write bunch of ifs and else to define each of the operators separatly like i did the division one.

``````template <typename t>
t reduceArray(t myArray[], int size, char op) {
if(size < 0 && op == '/')
return 1;
else if(size == 0)
return myArray[size]/reduceArray(myArray, size-1, op);
else
return reduceArray(myArray, size-1, op)/myArray[size];
}
``````

..
..
..
What I want to accomplish is this

``````int a=5, b=4;
cout<<calc(a,b,'+');

int calc(int a, int b, char c) {

return a c b;  //is there a way such that if c='+' it would add a and b
//                         if c='-' it would subtract
``````
3
Contributors
4
Replies
1 Day
Discussion Span
7 Months Ago
Last Updated
5
Views
rizwan.ali.1656
Newbie Poster
2 posts since Oct 2012
Reputation Points: 0
Skill Endorsements: 0

You can modify your function to take a function as one of the arguments. I find it easiest to add another template parameter to do this:

``````template< typename value_t, typename op_t >
value_t reduceArray( value_t myArray[], size_t size, value_t initial, op_t op) {
value_t out = initial;
for ( size_t i = 0; i < size; ++i )
out = op( out, myArray[ i ] );

return out;
}
``````

There are also a number of standard functional objects that you can pass in as the `op` variable, such as `std::plus`, `std::minus`, `std::multiplies` and `std::divides`. You can then call the function as:

``````double sum = reduceArray( array, 10, 0, std::plus< double >() );
``````

And `sum` will contain the sum of the elements in `array`.

If there's no standard one that does what you want, you can add your own :) It's good practice to inherit your functor from `std::unary_function` or `std::binary_function` as well.

Hope that helps.

ravenous
Practically a Master Poster
681 posts since Jul 2005
Reputation Points: 286
Skill Endorsements: 9

sorry I could make out how to work you function because it was giving me this error on line 5 that this function doesnt' take 2 parameters

Anyway here is the full function that i got to work, I have done the 4 operators separetly. This funcition is working perfectly but I wanted to know if this could be better used with second template type.

``````#include <iostream>

template <typename t>
t reduceArray(t myArray[], int size, char op) {
if(op == '/') {
if(size==0)
return myArray[size];
else
return reduceArray(myArray,size-1, op) / myArray[size];
}
else if(op == '+') {
if(size==0)
return myArray[size];
else
return reduceArray(myArray,size-1, op) + myArray[size];
}
else if(op == '-') {
if(size==0)
return myArray[size];
else
return reduceArray(myArray,size-1, op) - myArray[size];
}
else {
if(size==0)
return myArray[size];
else
return reduceArray(myArray,size-1, op) * myArray[size];
}
}

int main() {
double myArray[] = {4,7,1,2,9}; // you could make a int array and it would also work
int size = 5;
cout<<reduceArray(myArray,num-1,'/')<<endl;
cout<<reduceArray(myArray,num-1,'+')<<endl;
cout<<reduceArray(myArray,num-1,'-')<<endl;
cout<<reduceArray(myArray,num-1,'*')<<endl;
return 0;
}
/* Output
0.031746
23
-15
504
Press any key to continue . . .
*/
``````

The only thing changing is the operations so I know there is a better way to do this so i dont have to go thru all 4 instants.

Thanks

rizwan.ali.1656
Newbie Poster
2 posts since Oct 2012
Reputation Points: 0
Skill Endorsements: 0

Yea you can greatly reduce it to something like so http://codepad.org/ZR7IGhKu

firstPerson
Industrious Poster
4,046 posts since Dec 2008
Reputation Points: 851
Skill Endorsements: 15

sorry I could make out how to work you function because it was giving me this error on line 5 that this function doesnt' take 2 parameters

How were you trying to call it?

The only thing changing is the operations so I know there is a better way to do this so i dont have to go thru all 4 instants.

Yes, it's the way that I (and FirstPerson) have suggested :) Both of the methods are basically the same but not exactly what you want, since you require a recursive approach. The method suggested by FirstPerson and I use a loop instead, but you should be able to adapt it to use recursion instead. Incidentally, I'd say that this isn't a case where recursion is the way to go (unless it is specified that you MUST use recursion as an excercise for class).

The reason for not using recursion here is that a user can supply an arbitrarily large array for you to reduce. I'd imagine it's not uncommon for someone to want to sum an array of, say, a few thousand to a million elements. In this case, you will end up with a call stack a million functions deep! I don't think the stack will have enough space to support this. Remember, when you call the function you need space on the stack for all the local variables to the function and a pointer to the function itself. So in your case, this is a pointer to the function, a pointer to a `double` (the array), an `int` and a `char`. So, on a 2-bit system, that's something like 21-bytes of data per level of recursion.

Probably not essential for what you're doing right now, but worth thinking about :)

ravenous
Practically a Master Poster
681 posts since Jul 2005
Reputation Points: 286