通过在 C++ 中递归拆分数组来反转数组

Question

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

我最近使用 'logic2: D&C' 递归拆分数组以反转它们（更像是分而治之）。

（即如果输入 2,5,4,1，则输出应为 1,4,5,2）。

它像我刚才给出的例子一样通过了所有测试用例。然而，我觉得我并不真正理解递归的流程。我来这里是为了得到某人的帮助，如果可能的话，用示例流程图和值来解释 'logic2: D&C' 中发生的事情？

PS:

I took help from to implement this 'logic2: D&C'. Edits - Made little changes to argument list.

Answer 1

不清楚为什么使用了 std::string 类型的对象。要反转 char 类型的对象数组，无需使用 class sdt::string。这是低效的。该函数可以如下所示

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

Answer 2

分而治之算法的要点是在处理数据时将数据分解成越来越小的部分。

例如，如果您想反转数组，则应该发生以下情况：

1. 数据被分成两等份，并调换这些部分的顺序（所以后半部分变成前半部分，前半部分变成后半部分）
2. 然后将 2 个拆分的部分也分解为 2-2 个相等的部分，然后反转。
3. 以此类推，直到拆分为1个长度，因此无法进一步拆分，从而形成完全反转的数组。

Reading material on D and C algorithms