Recursive reduce

[rizwan.ali.1656]

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

[ravenous]

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.

[rizwan.ali.1656]

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

[mrnutty]

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

[ravenous]

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 :)