Recursion with Pointers in C: Concepts, Traces and Worked Examples

Recursion creates a new local pointer variable in every call, yet those pointer copies can still refer to and modify cells in the same array. If you track only values or only calls, you can miss either the pointer movement or the mutation that survives after return. sum_and_bump on {4, 1, 3} and print_reverse on {6, 2, 9, 5} illustrate valid array pointer arithmetic, base cases, call frames and return unwinding. For broader programming foundations, use the Coding & DSA course collection.

Recursion with a pointer: what is copied and what is shared

Recursion means a function calls itself with a smaller state. In a parameter such as int *p, the pointer value is passed by value. Each call owns a local p, but all those copies can point into the same array object.

For int a[] = {4, 1, 3}, the call sum_and_bump(a, 3) receives &a[0]. The next calls receive &a[1], &a[2], and finally the valid one-past pointer &a[3]. That final pointer must not be dereferenced.

Safe linear pointer recursion needs three things:

1. Test the base case before evaluating *p.

2. Reduce n to n - 1.

3. Move to the next element with p + 1.

Pointer arithmetic is scaled to the pointed-to type, so p + 1 advances by one int, not one byte.

A four-column method for tracing pointer recursion

Build the trace before predicting output. Use four columns: frame, local state (p index, n), work before recursion, and return value during unwind. Record the shared array separately because it does not belong to one frame.

For input length n, there are n non-base frames and one base frame at n == 0. With three elements, they are F0, F1, F2 and F3. Apply the stopping rule first. Then separate descent, where pointers move and mutations happen, from unwind, where each suspended expression receives the returned value from the next frame.

Worked example 1: return the original sum and increment every element

#include <stdio.h>

int sum_and_bump(int *p, int n) {
    if (n == 0) {
        return 0;
    }

    int before = *p;
    *p = before + 1;
    return before + sum_and_bump(p + 1, n - 1);
}

int main(void) {
    int a[] = {4, 1, 3};
    int total = sum_and_bump(a, 3);
    printf("%d | %d %d %d\n", total, a[0], a[1], a[2]);
    return 0;
}

The descent is:

Thus the exact output is 8 | 5 2 4. The total uses the saved original values, 4 + 1 + 3 = 8. The array retains the separate writes, so it ends as {5, 2, 4}. The function takes O(n) time and O(n) auxiliary call-stack space.

Call-stack view: local pointer copies, shared mutations and unwind

At maximum depth, the activation records are F0 (p=&a[0], n=3, before=4), F1 (p=&a[1], n=2, before=1), F2 (p=&a[2], n=1, before=3), and F3 (p=&a[3], n=0). Each before remains stored while its frame waits.

Advancing F1's p cannot change F0's local p. Writing through *p, however, changes a shared array cell that remains changed after all calls return. Frames leave in LIFO order, F3, F2, F1, F0, the same discipline explained in Stacks and Queues: Operations and Uses. A depth of n + 1 calls is still O(n) space. The active frames consume that recursive auxiliary space, not the array itself.

Worked example 2: print an array in reverse without moving elements

void print_reverse(const int *p, int n) {
    if (n == 0) {
        return;
    }
    print_reverse(p + 1, n - 1);
    printf("%d ", *p);
}

int b[] = {6, 2, 9, 5};
print_reverse(b, 4);

Descent visits (index 0, n=4), (index 1, n=3), (index 2, n=2), (index 3, n=1), then base (index 4, n=0). Nothing prints yet because printf follows the recursive call.

On unwind, the retained pointers print b[3] = 5, b[2] = 9, b[1] = 2, then b[0] = 6. The exact output is 5 9 2 6 , and the array stays {6, 2, 9, 5}. Moving printf before recursion would instead print 6 2 9 5 . The same placement idea powers the visit order in Binary Trees and Binary Search Trees, where a node visit can occur before, between or after recursive child calls.

Pointer-recursion traps and their exact corrections

Never dereference before the base test. int value = *p; if (n == 0) return 0; reads the one-past pointer in the base frame. Passing n = 4 for three-element a also leads beyond the array. Check n == 0 first and pass the actual element count.

Operator meanings matter:

• *p++ means *(p++): access the current element, then advance the local pointer.

• (*p)++ increments the pointed-to integer without advancing p.

• p + 1 computes the next-element pointer without changing this frame's p.

Avoid compact expressions such as *p + f(p++, n - 1). They read and modify p without the sequencing required for a defined C result. Also remember that changing a local pointer does not change the caller's local pointer, writes through copies can change shared elements, and sizeof(p) inside the function gives pointer size rather than array length. Recursion that changes neither p nor n does not approach this base case.

How exam-style questions test recursion with pointers

Typical question forms ask you to predict the return value and final array, find output order, identify a frame-local pointer index, detect a base-case or precedence error, or calculate calls, time and auxiliary space. Each form tests whether you can keep frame-local pointer state separate from shared memory.

Two rapid checks expose common mistakes:

• In the primary trace, F2 has p = &a[2], n = 1, and before = 3.

• For int c[] = {7, 2, 5}; and alt, where the base case returns *p at n == 1 and another frame returns *p - alt(p + 1, n - 1), evaluation is 7 - (2 - 5) = 7 - (-3) = 10, not (7 - 2) - 5 = 0.

After mastering a single recursive call per frame, move to memoisation. It becomes useful when a recurrence revisits the same state, unlike these linear examples.

Recursion with pointers in C: short version and next step

Use this six-point revision checklist:

1. Mark the base case before dereferencing.

2. Record the actual array length.

3. Label each frame's p index.

4. Separate local pointer changes from pointee mutations.

5. Trace descent before unwind.

6. Count both time and call-stack space.

The core result is simple: pointer copies are local to frames, but the memory reached through them can be shared. Continue with C Language Course: Concepts, MCQs & Coding for a structured route through C concepts and practice, or use the C Programming Course as a concise alternative.

Finish with a self-check. For int d[] = {2, 3, 4};, let product(d, 3) return 1 at n == 0 and otherwise return *p * product(p + 1, n - 1). Trace all four calls before checking the result: 2 * 3 * 4 * 1 = 24, with d unchanged.