string recursion(int arr[], int arrSize) {

if(arrSize == 1){
    return to_string(arr[0]);
}
string letterLeft, letterRight, letterFull;

//logic1: Normal Recursion
//letterFull = to_string(a[n-1])   " "   recursion(a, n-1);

//logic2: D&C ------------------------------------------------------ <
letterLeft  = recursion(arr, arrSize/2);
letterRight  = recursion(arr   arrSize/2, arrSize-arrSize/2)   " ";
letterFull  = letterRight   letterLeft;

return letterFull;
}

I recently used the 'logic2: D&C' for splitting an array recursively to reverse them (more like Divide and Conquer).

(i.e. if 2,5,4,1 is given as input, output should be 1,4,5,2).

It passed all test case like the example I just gave. Yet, I felt like I don't really understand the flow of recursion. I am here to get help from someone in explaining what happens in the 'logic2: D&C' step-by-step with an example flowchart & values if possible?

PS:

I took help from https://stackoverflow.com/a/40853237/18762063 to implement this 'logic2: D&C'. Edits - Made little changes to argument list.

CodePudding user response：

It is unclear why there are used objects of the type std::string. To reverse an array of objects of the type char there is no need to use the class sdt::string. This is just inefficient. The function can look the following way

void recursion( char arr[], size_t arrSize )
{
    if ( not ( arrSize < 2 ) )
    {
        std::swap( arr[0], arr[arrSize-1] );
        recursion( arr   1, arrSize - 2 );
    }
}

CodePudding user response：

The point of divide and conquer algorithms is breaking your data down to smaller and smaller pieces while processing it.

If you want to reverse an array for example, than the following should happen:

1. The data is split into 2 equal parts and the order of these parts gets switched (so the back half becomes the front half, and the front half becomes the back half)
2. The 2 split parts are then also broken down to 2-2 equal parts, and get reversed.
3. And so on, until the splits are 1 length, so they can't be split any further, resulting in a fully reversed array.

Reading material on D and C algorithms