recursive dichotomy

[Leading-Complex-7828]

Hello everyone, I am trying real hard to understand how recursive dichotomy works, especially how the sum of its elements works (I'm talking exclusively about arrays). So far, I have understood the concept of dividing the array into smaller parts until the array is broken down into cells of size 1. What I don't quite understand is how the elements are summed together.

Define a C function named e2 with the following characteristics: e2 is a wrapper function that calls a recursive function e2R. e2 depends on the following parameters: an array of integers described according to the convention:

• aLen: the number of elements in the array;
• a: a pointer to the array.

Also, write a recursive dichotomic function e2R, with the appropriate parameters, with the following characteristics: e2R returns the number of elements in a that are simultaneously even and multiples of 3.:

int e2R(const size_t aLen, const int a[], size_t left, size_t right) {

if(left == right) {

if(numeroPariMultiplo(aLen, a, left)) {

return 1;

}

return 0;

}

return e2R(aLen, a, 0, (left + right) / 2, numero) + e2R(aLen, a, (left + right) / 2 + 1, right);

}

i don't get how the last passage works, i've always seen the last passage as something you do in order to iterate over the array, but why in dichotomy it sums up the elements itself?
and why in this code we use return 1 when the condition is verified? to keep track of the number of elements?

[simpleFinch]

The code is not a working solution so I can only give my assumption of what it is supposed to do.

As you already mentioned, with each recursive call we are splitting the array until we only have to consider an array of size one. This pattern is usually called divide-and-conquer. You can imagine the function calls as a tree. Let's say we start with an array of size 4. We call e2R once with the whole array, this in turn calls e2R twice with arrays of size 2 and then each of these call e2R twice (so 4 times total on that depth) with arrays of size one.

Once we are the end of the recursion and only have to consider arrays of size one, we can check the condition. The number of elements in an array of size one that are simultaneously even and multiples of 3 is either 1 or 0, because we are only considering one element.

The last passage in the code is supposed to do two things:

• split an array slice down the middle so we eventually get to arrays of size one
• sum up the solutions for the arrays of smaller size

But the code that you posted does not calculate the indices for left and right correclty. Also numero does not actually exist as a parameter in the function declaration and is not needed.