Recursion over a bounded array prefix

Know exactly which elements belong to the call

A recursive array helper needs both a place to read from and a limit on what it may read. In this lesson, a call handles the first n elements of one array, returns a result for exactly those elements, and reaches an empty prefix before it tries another read. You will trace the reads and returned values without imagining that recursion copies or physically shortens the array.

Read these lessons first, in this order:

1. Recursion: base case and call stack: separate invocations and preserved caller state.
2. Recursion termination and base case design: admitted inputs, a decreasing nonnegative measure and guards before unsafe operations.
3. Recursion: returned values and pending calculations: a child’s returned result and the caller’s remaining work.

You also need ordinary int variables and copied arguments, if, return, initialized fixed-size arrays and zero-based indexing. For int a[4], the element indices are 0, 1, 2 and 3. This lesson explains the limited array-parameter behavior needed here; prior pointer arithmetic is not required. It covers small, read-only, one-child recursion. Array mutation, pointer arithmetic, dynamic allocation, branching recursion and formal complexity analysis are outside this lesson.

Our explicit array plus length contract

All shown programs use C11. For every helper in this lesson:

• The caller supplies an existing array of int whose actual capacity is from 1 through 6. Capacity means how many element slots that array actually has.
• Every array element is initialized and lies from -9 through 9. The array remains alive and unchanged for the entire call and its recursive children.
• The length n is an integer satisfying 0 <= n <= capacity. It selects the prefix a[0] through a[n - 1] when n > 0.
• At n == 0, the selected prefix is empty. No array element belongs to it and no array read is needed. We still pass the existing array. We do not declare a zero-length C array, and null-pointer arguments are outside this lesson’s contract.
• Each non-base invocation makes exactly one child call with the same array and length n - 1. No child changes array elements or the starting pointer.

Capacity belongs to the actual array object; n is the chosen logical length. An array with four stored elements can supply prefixes of length 0, 1, 2, 3 or 4. A length of 3 does not select index 3: it selects three elements, ending at index 2.

The contract is a promise the caller must meet, not an automatic run-time check. The helper is not given capacity separately, and C does not discover and enforce this bound from the a[] parameter. A negative length, an oversized length or unsuitable storage is outside the promise. Do not execute those calls to look for a reliable output.

These bounds keep every prefix sum between -54 and 54 and every count between 0 and 6, representable even with C’s minimum required int range. Assume enough execution resources for these short chains. This is not a claim about arbitrary input sizes or a generally safe recursion depth.

Return meaning before code

Define prefix_sum(a, n) to return the sum of exactly the first n elements. The empty sum is 0. For positive n, separate the chosen prefix into:

• the first n - 1 elements, handled by the child;
• the one remaining element, a[n - 1], handled by this call.

The two parts have no overlap and leave no chosen element out. Therefore this call must return child + last. It must not add n, add every element again or include the first excluded element a[n].

Predict the two integers printed by this program.

#include <stdio.h>

int prefix_sum(const int a[], int n) {
    if (n == 0) {
        return 0;
    }
    int last = a[n - 1];
    int child = prefix_sum(a, n - 1);
    return child + last;
}

int main(void) {
    int values[4] = {4, -1, 7, 3};
    int used = 3;
    int answer = prefix_sum(values, used);
    printf("%d %d\n", answer, used);
    return 0;
}

The output is 10 3. The answer is 4 + (-1) + 7 = 10; the stored fourth element 3 is outside the requested prefix. The variable used in main stays 3.

Worked trace Reads downward and sums upward

Write each call’s own length and the result it is waiting for. In this particular function, last is read before the child call; the addition happens after the child returns.

The read indices are 2, 1, 0. The returned prefix sums, from the base upward, are 0, 4, 3, 10. Do not confuse those two orders or mistake a decreasing length for a returned sum. A waiting call keeps its own initialized last and n.

Starting with length 3 produces four helper invocations, including the empty-prefix base call, and three element reads. Those are source-level tracing counts; they do not specify physical stack bytes or compiler optimizations. In the complete program above, only main prints.

The array remains while each length is copied

In a function parameter, const int a[] is adjusted by C to a pointer parameter. For these calls, its value designates the first element of the caller’s array. That pointer value is passed by value, and each recursive call passes the same value onward. No copy of all the array elements is made by this declaration or by the recursive call.

The ordinary int n is also passed by value. The child gets its own length n - 1; it does not change the parent’s n or main’s used. The parent at length 3 stays a length-3 call while its child handles length 2. The array’s allocated size and stored elements do not shrink.

const here prevents assigning to an element through this parameter. It does not make a private array copy or make the original array impossible to change through every other reference. Our contract separately requires the storage to remain unchanged during the computation; the shown helpers only read it. With an appropriately writable parameter, a different helper could change shared elements, which is outside our present scope.

Why the first read is safe

Check safety separately from the returned calculation:

1. At n == 0, the executed return 0 comes before a[n - 1]. No attempt is made to read index -1.
2. Otherwise the contract and failed base test give 1 <= n <= capacity. Hence 0 <= n - 1 < capacity, so this call’s read is within the array and within its selected prefix.
3. The child receives the same live array and a length from 0 through capacity - 1. It satisfies the same contract. Its prefix is exactly one element shorter.
4. The nonnegative integer length decreases by 1 on each child call and stops at 0. Once the child returns, one small addition completes the caller’s exact promised sum.

Do not move the array read before the zero-length guard: an empty-prefix call would then try index -1 before it could return. Do not replace a[n - 1] with a[n]: when n == capacity, that would read one past the array. When n < capacity, it might still be within the stored array, but it is outside the selected prefix and gives the wrong decomposition. We diagnose these defective changes without executing them.

An early return protects only the expressions it prevents from running. It does not fix a caller that supplies a length larger than the actual array capacity. Likewise, a chain reaching 0 is insufficient if it made an invalid read on the way.

Boundary checks for the same four element array

For values = {4, -1, 7, 3}:

Lengths -1 and 5 are outside this array’s contract and are not test runs. Notice that a length of 0 does not mean an element with value 0. It means there are no selected elements at all. A length-1 prefix containing the value 0 would still read one element and make a base-case child.

Worked trace Count a property of the same prefix

Now define count_positive(a, n) to return the number of positive elements in the first n positions. Its base count is 0. A positive last element contributes 1; zero or a negative element contributes 0. The child still handles precisely the first n - 1 positions.

#include <stdio.h>

int count_positive(const int a[], int n) {
    if (n == 0) {
        return 0;
    }
    int last = a[n - 1];
    int child = count_positive(a, n - 1);
    if (last > 0) {
        return child + 1;
    }
    return child;
}

int main(void) {
    int values[5] = {0, -2, 5, 0, 3};
    printf("%d\n", count_positive(values, 5));
    return 0;
}

The program prints 2. The five-element prefix contains the positive values 5 and 3. Returning values are counts, not sums of those values.

Every row follows the stated return meaning. When the last element is not positive, returning the child unchanged is correct: the prefix became longer, but the count did not increase. The safety argument uses the same array, length and early-return conditions as prefix_sum.

A precise analogy

Imagine one row of six numbered boxes on a table. A request slip says, “Use only the first four boxes.” A smaller request says, “Use only the first three.” The boxes stay on the same table; the new slip does not cut away or copy a box. Each waiting slip keeps its own requested count and the one value it already read. A slip requesting no boxes sends back 0 without opening any box.

This analogy models shared array storage, separate copied lengths and an empty prefix. It does not describe physical stack layout, concurrent workers or an automatic barrier that enforces the length for you.

Key box Keep storage length and result separate

• Storage: the original live array; its capacity does not shrink during these calls.
• Length: this invocation’s copied n, choosing indices 0 through n - 1 when positive.
• Empty prefix: length 0; return before any element read.
• Child contract: the same array and the first n - 1 elements.
• Return meaning: an exact sum or count for this prefix, not necessarily its length or last value.
• Safety: prove the read index is valid and the child preserves the contract. Termination alone is not enough.
• const supports read-only access through this parameter; it does not copy the array.

Six original practice questions

Choose exactly one of four options for each question. These are original standard-practice exercises, not official previous-year questions or a full exam mock. Use the exact helper definitions above where named and the stated bounded contract throughout. Question 6 supplies a complete separate C11 program. It introduces void: that function returns no value, and return; only ends its invocation.

Question 1

Use prefix_sum exactly as defined in the first worked example. For int values[4] = {4, -1, 7, 3}, what does prefix_sum(values, 3) return?

A. 13 B. 3 C. 10 D. 9

Question 2

Use the same prefix_sum. Given int box[1] = {8}, which description of prefix_sum(box, 0) is correct?

A. It returns 0, reads no array element and makes no recursive child call. B. It returns 0 after reading box[0]. C. It returns 8 because the array contains one element. D. It makes a child call with n = -1 before returning 0.

Question 3

In the first complete program, main sets used = 3 and calls prefix_sum(values, used). Which statement correctly describes the length arguments and array storage?

A. All invocations share one n object, so used becomes 0. B. Each child gets a new shorter array containing copies of the prefix elements. C. const makes a private array copy for each invocation and freezes every possible reference to the original. D. Each invocation has its own copied n; all these calls refer to the same array storage. used remains 3 and the elements are unchanged.

Question 4

Let capacity be the actual number of stored elements and admit only 0 <= n <= capacity. Which explanation establishes safe indexing in prefix_sum for every admitted n?

A. a[n] is always the last valid element because n is the length. B. The n == 0 return happens before any read. Otherwise 0 <= n - 1 < capacity, and the child keeps the same array with the shorter valid prefix. C. Writing a[] as a parameter makes C automatically check the length before each access. D. Negative n values are also safe because repeatedly subtracting 1 must eventually reach 0.

Question 5

Use count_positive exactly as defined in the second worked example. For int values[5] = {2, 0, -3, 4, -1}, what does count_positive(values, 4) return?

A. 3 B. 2 C. 4 D. 6

Question 6

Which sequence of integers does this program print? Ignore the final space and newline. The same array-and-length contract applies. A void function returns no value; return; just ends that invocation.

#include <stdio.h>

void show_prefix(const int a[], int n) {
    if (n == 0) {
        return;
    }
    show_prefix(a, n - 1);
    printf("%d ", a[n - 1]);
}

int main(void) {
    int values[4] = {4, 2, 5, 9};
    show_prefix(values, 3);
    printf("\n");
    return 0;
}

A. 5 2 4 B. 4 2 5 9 C. 0 1 2 D. 4 2 5

Answers and option feedback

Answer 1: C

A is incorrect. 13 includes all four stored elements. A length of 3 excludes values[3], whose value is 3.

B is incorrect. 3 is the supplied length, not the sum of the selected elements.

C is correct. The selected indices are 0, 1 and 2, so the return is 4 + (-1) + 7 = 10.

D is incorrect. 9 is 4 + (-1) + 7 - 1; it counts the negative element twice. Each selected element contributes once.

Answer 2: A

A is correct. The first condition is true, so return 0 ends this invocation before the read and the recursive call.

B is incorrect. The read appears after an executed return, so no element, including box[0], is read.

C is incorrect. The selected prefix has length 0 even though backing storage exists. Its sum is 0.

D is incorrect. The base case returns before n - 1 is passed anywhere. The chain ends at 0.

Answer 3: D

A is incorrect. Ordinary int arguments are passed by value. A child receiving 0 does not change the waiting caller’s n or main’s used.

B is incorrect. The array elements are not copied by this parameter declaration. Only the logical prefix length becomes smaller.

C is incorrect. const int a[] prevents element assignments through this parameter; it does not clone the array or globally freeze the original.

D is correct. The pointer value designating the first element is copied, as is n. The target array remains the same, and this helper only reads it.

Answer 4: B

A is incorrect. The prefix indices end at n - 1. At n == capacity, a[n] would be one past the array and cannot be read; for smaller n it is still outside the selected prefix.

B is correct. A positive admitted n gives a valid last index, and n - 1 stays between 0 and capacity. The base case needs no element. This argument applies again to each child.

C is incorrect. This array parameter carries no automatic length check. The caller must meet the contract and the code must honor it.

D is incorrect. Negative lengths are outside the contract. Subtracting 1 moves a negative integer farther from 0, and the earlier array access is already unjustified. Do not run that call.

Answer 5: B

A is incorrect. 3 counts the zero as well as the two positive elements. The test is last > 0, so zero does not contribute.

B is correct. The chosen prefix is {2, 0, -3, 4}; only 2 and 4 are positive. Returning counts for n = 0 through 4 are 0, 1, 1, 1, 2.

C is incorrect. 4 is the selected length, not the number of positive elements.

D is incorrect. 6 is the sum of the positive values 2 and 4. This function adds 1 for a positive element, not the element’s value.

Answer 6: D

A is incorrect. This is reverse element order. Here printf runs after the child, so the smallest nonempty prefix prints first.

B is incorrect. Length 3 excludes the stored fourth element 9.

C is incorrect. Those are the selected indices. printf receives the element a[n - 1], not the index n - 1.

D is correct. The n = 0 call prints nothing. Returning calls with n = 1, 2 and 3 print a[0] = 4, a[1] = 2 and a[2] = 5 in that order.

Before moving on

If you included an extra element, label the valid prefix indices before tracing. If you made the parent’s length turn into 0, draw separate n entries beside one unchanged array. If you counted values instead of elements, write the promised return meaning above each row. If an empty call tried to read an element, move back to the guard and check what can execute before it.

For a new helper, state the storage and length contract, the empty-prefix result, the child’s exact task and the one element left for the caller. Test the empty, one-element and full prefixes first, then mixed positive, zero and negative values. A correct-looking answer does not excuse an invalid index.

This lesson is one introductory step in GATE CS preparation. It does not establish complete C, data-structures or recursion coverage. Branching recursion and formal recurrence or resource analysis require later lessons.

Source and scope note

The previously reviewed lessons checked the official GATE 2027 CS syllabus on 13 October 2026 and recorded recursion as a relevant Programming and Data Structures topic. This offline continuation uses that syllabus context; it does not claim a new live verification. The explanations, programs and six questions here are original teaching material. C11 is the teaching language choice, not a claim about the official exam’s language version. No official previous-year question is reproduced or claimed.