Recursion over arrays

Overview

Arrays recurse naturally once you see them as "one element plus a smaller array". Handle the last (or first) element directly, recurse on the remaining n-1, and combine the two results. Summing is the gentlest case — a[n-1] + sum(a, n-1) — and finding a maximum shows the pattern where the combination is a comparison rather than an operator. The base case is the empty array (sum 0) or the single-element array (its own maximum), and choosing the right one matters: amax cannot meaningfully answer for an empty array, so its base case must be n == 1.

Why it matters

This decomposition is the mental model behind divide-and-conquer and behind every fold or reduce operation you will meet in other languages. More practically, it teaches you to reason about a function's contract at the boundary — what does this return for an empty input? — which is exactly where array bugs live.

Core concepts

Shrink by one. f(a, n) = combine(a[n-1], f(a, n-1)). Working from the end keeps the pointer fixed and only the length changes, which is easy to reason about.

Or shrink the pointer. f(a+1, n-1) walks forward instead. Equivalent, but now both the base pointer and the length move — be consistent so the two never disagree.

Choosing the base case. For a sum, the empty array is 0 — the identity element, so n <= 0 is natural and total. For a maximum there is no identity, so the base case must be n == 1, and the function has a genuine precondition that n >= 1.

The combination step. Sum uses +; maximum uses a comparison; a search uses a short circuit. The recursion shape is identical — only the combine changes.

Depth equals length. This is linear recursion: an array of 100,000 elements builds 100,000 frames. That is a real limitation compared with a loop, and the reason production code sums arrays iteratively.

Syntax notes

/* empty array sums to 0 - the identity, so n <= 0 is a total base case */
long long asum(const int *a, int n) {
    if (n <= 0) return 0;
    return a[n-1] + asum(a, n - 1);
}

/* no identity for max, so the base case is a single element (precondition: n >= 1) */
int amax(const int *a, int n) {
    if (n == 1) return a[0];
    int m = amax(a, n - 1);
    return (a[n-1] > m) ? a[n-1] : m;
}

Key points:

• a[n-1] is the last element; the recursive call covers a[0 .. n-2].
• asum is total (safe for n == 0); amax is partial and needs its precondition documented and checked by the caller.
• long long for the sum — many int values easily overflow 32 bits.

Lesson

Arrays recurse naturally: handle the last (or first) element, then recurse on the shorter remainder. Summing and finding a maximum both combine one element with the result of the smaller subproblem.

Code examples

#include <stdio.h>
static long long asum(const int*a,int n){ if(n<=0) return 0; return a[n-1] + asum(a,n-1); }
static int amax(const int*a,int n){ if(n==1) return a[0]; int m=amax(a,n-1); return a[n-1]>m?a[n-1]:m; }
int main(void){
    int a[]={4,8,15,16,23,42};
    printf("sum = %lld\n", asum(a,6));
    printf("max = %d\n", amax(a,6));
    return 0;
}

Line by line

Common mistakes

Off-by-one indexing; wrong base case (n==0 for sum, n==1 for max).

Debugging tips

Compiler errors and warnings:

• -Wsign-compare if n is size_t and you test n <= 0 — with an unsigned type that is only true at 0, and n - 1 on 0 wraps to a huge value. Keep n signed here.
• warning: array subscript is below array bounds for an unguarded a[n-1] when n is 0.

Runtime symptoms:

• Crash on an empty array. amax(a, 0) recurses to amax(a, -1) and beyond, or reads a[-1]. That function requires n >= 1.
• Sum is wrong or negative for large arrays. int overflow — accumulate in long long.
• Stack overflow on a big array. Expected: depth equals length. Use a loop for large inputs.
• Off-by-one, first or last element missed. Mixing the two styles — a[n-1] with f(a+1, n-1) skips and repeats elements. Pick one and stay with it.

Technique: test with sizes 0, 1 and 2. Almost every bug in this shape appears at one of those three.

Memory safety

• a[n-1] with n == 0 reads a[-1] — out of bounds. asum is safe because the guard comes first; amax is safe only if the caller respects n >= 1. State the precondition and enforce it at the boundary.
• Unsigned length types are dangerous here. With size_t n, n - 1 at 0 wraps to SIZE_MAX and the recursion runs off the end of memory. Use a signed length, or guard n == 0 explicitly before subtracting.
• Depth equals array length. A large array will exhaust the stack; that is a crash with no recovery path, so bound the size or iterate.
• const int *a documents that the array is not modified and lets the compiler catch accidental writes.
• Signed overflow in the sum is undefined behaviour, not a wrap — widen the accumulator.

Real-world uses

Concrete uses: The fold/reduce pattern in functional languages is exactly this decomposition. Divide-and-conquer sorts split rather than peel, but share the "solve smaller, combine" structure. Recursive array processing is common in teaching and in tree-shaped data (where the branching makes recursion genuinely the right tool) even though flat arrays are usually iterated in production.

Professional best practices:

Beginner:

• Decide the empty-array answer before writing the function.
• Test sizes 0, 1 and 2 first.

Intermediate:

• Prefer iteration for flat arrays in production code; reserve recursion for branching structures.
• Document partial functions' preconditions (amax requires n >= 1) and check them at the API boundary.
• Keep length parameters signed, or guard before subtracting, to avoid unsigned wrap-around.

Practice tasks

1. (Beginner) Recursive sum. Implement long long asum(const int *a, int n) returning 0 for an empty array. Example: {4,7,2} -> 13. Concepts: identity base case.

2. (Beginner) Recursive maximum. Implement int amax(const int *a, int n) with the n == 1 base case. Example: {4,7,2} -> 7. Concepts: partial functions, preconditions.

3. (Intermediate) Recursive contains. Implement int contains(const int *a, int n, int t) that short-circuits on the first match. Concepts: combining with a short circuit.

4. (Intermediate) Head-recursive variant. Rewrite asum using asum(a+1, n-1) and confirm both give identical results. Concepts: pointer-shrinking vs length-shrinking.

Summary

Treat an array as "one element plus a smaller array": handle a[n-1], recurse on n-1, and combine. Only the combine step changes between summing, maximising and searching. Choose the base case from whether the operation has an identity — summing an empty array is naturally 0, but a maximum has no answer for an empty array, so its base case is a single element and n >= 1 becomes a real precondition. Keep the length signed (or guard before subtracting), widen the accumulator against overflow, and remember the recursion depth equals the array length, which is why production code usually loops instead.

Practice with these exercises

• Recursive array sum
• Recursive array max