小编rob*_*ega的帖子

void recursiveInsertionSort(vector<int> &arr, int n) {
    if (n <= 1)
        return;
    recursiveInsertionSort(arr, n - 1);
    int val = arr[n - 1], j = n - 2;
    for (j = n - 2; j >= 0 && arr[j] > val; --j)
        arr[j + 1] = arr[j];
    arr[j + 1] = val;
}

我认为空间复杂度是常数（O(1)），因为我通过引用传递数组。

但我被告知它实际上是 O(n)。这是为什么 ？