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.
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 );
}
}