Find the Largest Element of an Array using Recursion

The largest value in n elements comes from one smaller answer and one comparison

Define largest(a, n) as the largest value in the prefix from index 0 through index n - 1. For the running array [4, 2, 7, 1], largest(a, 4) inspects all four values. Instead of solving all four at once, separate the last value, a[3], from the first three values. The first three are handled by largest(a, 3), and the final answer is the larger of largest(a, 3) and a[3].

This reduction gives largest(a, 4) = max(largest(a, 3), 1). The recursive call finds the largest value in [4, 2, 7], while the current call supplies the omitted value 1. Each call therefore asks a smaller call for a result and combines that result with exactly one array element.

int largest(const vector<int>& a, int n) {
    if (n == 1) return a[0];
    return max(largest(a, n - 1), a[n - 1]);
}

A one-element prefix already contains its own largest value

When n is 1, the inspected prefix is [4]. Its only element must be the largest value in that prefix, so largest(a, 1) returns a[0], which is 4. This is the stopping point because making another call would ask for a prefix with no smaller positive length.

The function requires n to be at least 1. There is no array element that can serve as the answer for n = 0, so an empty prefix needs a separate rule such as a special return value or an exception. This function avoids that case by defining its input as a non-empty prefix.

Each returned maximum becomes the candidate for the caller

The calls first move down to the one-element prefix, then return one answer at a time. For the running array, the prefixes of lengths 1 through 4 produce the return values 4, 4, 7, and 7. Each value is the maximum of its own prefix, not merely the value at the current index.

The return expression passes the recursive result directly into the comparison. At n = 3, the result 4 from the shorter prefix is compared with 7, so the call returns 7. At n = 4, that 7 is compared with 1, so the smaller final element cannot replace it. No global or shared variable is needed because every caller receives the information it needs as a return value.

One constant-time comparison per level makes the cost linear

For n greater than 1, one call solves a prefix of length n - 1 and then performs one comparison with a[n - 1]. That gives the recurrence T(n) = T(n - 1) + Theta(1), with T(1) = Theta(1). Expanding the recurrence adds one constant-time comparison for every element after the first.

For [4, 2, 7, 1], the function makes n - 1 = 3 comparisons: max(4, 2), max(4, 7), and max(7, 1). In general, the time complexity is Theta(n), because the function processes each prefix level once and does constant work at each level.

The calls remain active while the smaller prefix is being solved, so the recursion stack contains Theta(n) call frames at its deepest point. The extra space is therefore Theta(n). This analysis assumes the array is passed without copying it, as with a C++ reference or a Java array reference.