Printing an Array Recursively Depends on Where You Print

Each recursive call is responsible for exactly one array index

For the array [4, 2, 7, 1], let printArray(a, n, i) handle the element at index i. A non-base call prints a[i], then makes the recursive call for i + 1. The first call starts with i = 0, so responsibility moves from the first element towards the end of the array one index at a time.

void printArray(int a[], int n, int i) {
    if (i == n) return;

    cout << a[i] << " ";
    printArray(a, n, i + 1);
}

printArray(a, 4, 0);

Call                  Value printed
printArray(a, 4, 0)   a[0] = 4
printArray(a, 4, 1)   a[1] = 2
printArray(a, 4, 2)   a[2] = 7
printArray(a, 4, 3)   a[3] = 1
printArray(a, 4, 4)   base case, nothing printed

The stopping call must return before it accesses the array

The array has four elements, so its valid indices are 0 through 3. When i becomes 4, there is no element to print. The call printArray(a, 4, 4) must return immediately, before any expression tries to read a[4]. That call is still useful because it stops the chain after index 3 has been handled.

void printArray(int a[], int n, int i) {
    if (i == n) return;

    cout << a[i] << " ";
    printArray(a, n, i + 1);
}

Stopping at i == n - 1 would stop too early for this array. The call with i = 3 would return before printing a[3], so the final value 1 would be skipped. Stopping at i == n lets the call at index 3 print 1, then lets the call at index 4 return safely.

Printing before the recursive call preserves left-to-right order

The recursive call does not force one output order by itself. The print statement's position decides when each value is produced. If you print a[i] before calling printArray(a, n, i + 1), each value appears as the calls descend: 4, then 2, then 7, then 1.

void printArray(int a[], int n, int i) {
    if (i == n) return;

    cout << a[i] << " ";
    printArray(a, n, i + 1);
}

// Output: 4 2 7 1

If you move the same print operation below the recursive call, the calls first descend to i = 4 without printing. Then they return one at a time, and each call prints its own value during unwinding. The call for index 3 prints 1 first, followed by 7, 2, and 4, so the output becomes 1 7 2 4.

void printArray(int a[], int n, int i) {
    if (i == n) return;

    printArray(a, n, i + 1);
    cout << a[i] << " ";
}

// Output: 1 7 2 4

void printArray(int a[], int n, int i) {
    if (i == n) return;

    printArray(a, n, i + 1);
    cout << a[i] << " ";
}

Visiting every element takes linear time and linear stack space

For [4, 2, 7, 1], four calls process array elements, with i equal to 0, 1, 2, and 3. A fifth call with i = 4 checks the base case and returns. The amount of work grows with the number of elements, because each element-processing call performs constant work and makes one recursive call.

T(k) = T(k - 1) + Theta(1)
T(0) = Theta(1)

For [4, 2, 7, 1]:
4 processing calls + 1 stopping call

Time: O(n)
Auxiliary stack space: O(n)

The recurrence T(k) = T(k - 1) + Theta(1), with T(0) = Theta(1), gives O(n) time. The calls remain active while the next index is processed, so the deepest chain contains one call for each element plus the stopping call. That call stack uses O(n) auxiliary space.