# Finding the largest value in array – Recursion

Posted on

Problem

I know this may be a silly question (I’m just learning about recursion, and I think there are still things that are still not clear to me.), but… is this a good implementation of a recursive function to find the maximum number in an array?

``````#include <iostream>
#include <cstdlib>

using std::cout;
using std::endl;

/* function prototype */
int find_max(const int [], int);

/* main function */
int
main(void)
{
int array[] = {2, 6, 8, 23, 45, 43, 51, 62, 83, 78, 61, 18, 71, 34, 72};
int size = sizeof(array) / sizeof(array[0]);

cout << "HIGHEST: " << find_max(array, size) << endl;
exit(EXIT_SUCCESS);
}

/* function definition */
int
find_max(const int array[], int size)
{
int i = 1;
int highest = array[0], l = 0;

if (i < size)
l = find_max(array+i, size-1);

if (l > highest)
highest = l;

return highest;
}
``````

output:

``````./main
HIGHEST: 83
``````

what I basically want to do is implement the same algorithm using recursive structure.
or rather implement the function below.

``````int
find_max(const int array[], int size)
{
int highest = array[0];

for (int i = 1; i < size; i++)
{
if (array[i] > highest)
highest = array[i];
}
return highest;
}
``````

Solution

I respectfully disagree with the advice to prefer iteration to recursion. I personally prefer to express most algorithms recursively. It’s much more suitable to a kind of programming style, using only static single assignments, where certain kinds of bugs become impossible to write without the compiler catching them. It’s often easier to reason about the code and prove it correct. And, properly-written, it’s just as efficient.

For several decades, programmers were taught to turn recursive functions into iterative loops, but that was originally because compilers used to be bad at optimizing recursive calls. That’s no longer as true as it was, so it’s now a matter of personal preference.

Besides, you’ll have to learn to program in a functional language that has only recursive calls and not loops, if you want a computer science degree these days.

So, how do we write this in a recursive call? For the sake of explaining exactly what I’m doing and why, I’m going to ridiculously overdo it. This would be one line of code in a functional language. With that in mind, in functional style, all the local state of the loop becomes parameters of a function, and whenever that local state changes, such as the loop incrementing its counter and repeating, become the function returning a call to itself.

What, then, is the local state? The code you want to transform starts out as

``````int
find_max(const int array[], int size)
{
int highest = array[0];

for (int i = 1; i < size; i++)
{
if (array[i] > highest)
highest = array[i];
}
return highest;
}
``````

There are four local variables here: `array`, `size`, `i` and `highest`. You already figured out, in a similar question you asked, that you can reduce this to three by searching from back to front instead of front to back; the loop `for ( auto i = size; i > 0; --i )` only uses `size` to initialize `i`, and only need `i` thereafter. Another way to bring this down to three state variables would be to recursively search the subarray starting at `array+1` of length `size-1`, the subarray starting at `array+2` of length `size-2`, and so on. Another common idiom for this is to use a `current` and `end` pointer, and stop when `current` is equal to `end`. Here, let’s use the same approach you did in your other question and count down.

Since the local update we want to keep around consists of `array`, `i`, and `highest`, our function signature should look like

``````int find_max( const int array[], size_t i, int highest )
``````

Only, like in my other answer, we want this to be `constexpr` so it can perform constant-folding, and `noexcept` to help the compiler optimize. On top of that, the only time the state chances is when we make a tail-recursive call, and we can only update the entire state together, so there is no way we can accidentally forget to update one of the state variables or update it twice. So, with static single assignments, the function declaration becomes,

``````constexpr int find_max( const int array[], size_t i, int highest ) noexcept
``````

Only, the original caller passed in `array` and `size`, so this is actually a helper function that `find_max` will call, and `find_max` itself will use the same interface as before. So, we actually want a pair of functions:

``````static constexpr int find_max_helper( const int array[], const size_t i, const int highest ) noexcept;

constexpr int find_max( const int array[], const size_t size );
``````

We want to make sure to write only tail calls, so our function should have an `if`/`then`/`else` structure, where each branch returns either an `int` or a function call. Let’s see the original function again.

``````int
find_max(const int array[], int size)
{
int highest = array[0];

for (int i = 1; i < size; i++)
{
if (array[i] > highest)
highest = array[i];
}
return highest;
}
``````

What I ideally try to do (but don’t always, especially for really short examples like this) is write the contract for my functions in a comment first. In this case, the name of the function and its parameters are self-explanatory, but that might look like:

``````constexpr int find_max( const int array[], const size_t size )
/* Returns the maximum value of the array of the given size.
*/
``````

Only, wait, what is the maximum value of a zero-length array? Your implementation just checks `array[0]` unconditionally, so `find_max( NULL, 0 )` would have undefined behavior, usually a segmentation fault. You always, always, always check for a buffer overrun in C and C++. It is never too early to get in the habit. I seriously mean it. That could be an `assert()`, but for this example, let’s throw an `std::logic_error` exception.

And there are several possible ways we could have handled this, so it actually becomes important to document the behavior of the function in this case, or at least warn anyone who uses this function what assumptions it makes.

So the first few lines of our function will look like this:

``````constexpr int find_max( const int array[], const size_t size )
/* Returns the maximum value of the array of the given size.
* Throws std::logic_error if size is 0.
*/
{
if ( size == 0 ) {
throw std::logic_error("Max of a zero-length array");
}
``````

What about the rest? We’re reducing the array from back to front and you initialize `highest` to the first element before you start looping. We refactored to search from the back, so the first element we check is now the rightmost instead of the leftmost, and we replace iterations of the loop with tail-calls to a helper function, but we can follow the exact same logic. our initial state has `i` equal to `size-1` (and we just checked that `size` is greater than `0`, so this is in bounds), `array` equal to the value we were passed, and `highest` equal to the last element of `array`, which is `array[size-1]`.

So far, then, we have

``````static constexpr int find_max_helper( const int array[], const size_t i, const int highest ) noexcept;
/* Searches the array from index i to 0 for an element greater than highest.
* Intended to be called only from find_max.
*/

constexpr int find_max( const int array[], const size_t size )
/* Returns the maximum value of the array of the given size.
* Throws std::logic_error if size is 0.
*/
{
if ( size == 0 ) {
throw std::logic_error("Max of a zero-length array");
}

return find_max_helper( array, size-1, array[size-1] )
}
``````

Now we just need to implement `find_max_helper`. It’s pretty straightforward: check whether we’ve reached the start of the array, and if not, find the new maximum and recurse. So, there are three branches: the termination check, the case where the current element is higher, and the case where it isn’t.

``````static constexpr int find_max_helper( const int array[], const size_t i, const int highest ) noexcept
/* searches the array from index i to 0 for an element greater than highest.
* Intended to be called only from find_max.
*/
{
if ( i == 0 ) {
return highest;
} else if ( array[i-1] > highest ) {
return find_max_helper( array, i-1, array[i-1] );
} else {
return find_max_helper( array, i-1, highest );
}
}
``````

You could also express this as a series of `if` statements that either return or fall through, making it clearer that the function always terminates in a valid `return`) or in a nested ternary expression like in your other question for review.

Putting it all together, and setting our types correctly in the `main` test driver, we get:

``````#include <cassert>
#include <cstdlib> // for EXIT_SUCCESS
#include <iostream>
#include <stdexcept> // For runtime_error

using std::cout, std::endl, std::size_t;

static constexpr int find_max_helper( const int array[], const size_t i, const int highest ) noexcept
/* Searches the array from index i to 0 for an element greater than highest.
* Intended to be called only from find_max.
*/
{
if ( i == 0 ) {
return highest;
} else if ( array[i-1] > highest ) {
return find_max_helper( array, i-1, array[i-1] );
} else {
return find_max_helper( array, i-1, highest );
}
}

constexpr int find_max( const int array[], const size_t size )
/* Returns the maximum value of the array of the given size.
* Throws std::logic_error if size is 0.
*/
{
if ( size == 0 ) {
throw std::logic_error("Max of a zero-length array");
}

return find_max_helper( array, size-1, array[size-1] );
}

int main(void)
// Test driver for find_max.
{
constexpr int array[] = {2, 6, 8, 23, 45, 43, 51, 62, 83, 78, 61, 18, 71, 34, 72};
constexpr size_t size = sizeof(array) / sizeof(array[0]);

cout << "HIGHEST: " << find_max(array, size) << endl;
return EXIT_SUCCESS;
}
``````

The call to `find_max` compiles to

``````mov     esi, 83
``````

This is why you always write your functions as `constexpr` when you can. In the real world, that can typically make a program run 33% faster. If you want to actually see the generated code, you can force the compiler to actually generate the code by making a call to some data it cannot constant-fold.

``````int main(void)
// Test driver for find_max.
{
#if 0
constexpr int array[] = {2, 6, 8, 23, 45, 43, 51, 62, 83, 78, 61, 18, 71, 34, 72};
constexpr size_t size = sizeof(array) / sizeof(array[0]);
#endif

extern const int array[];
extern const size_t size;

cout << "HIGHEST: " << find_max(array, size) << endl;
return EXIT_SUCCESS;
}
``````

What this will tell you is that modern compilers don’t literally compile this as written. What they actually do is figure out for you that you are doing a reduction of the array with the max operation, which is associative and therefore can be automatically vectorized.

And, in fact, most code with loops or a tail-recursive accumulator aren’t supposed to literally iterate or recurse one element at the time. We actually want the compiler to notice that a vectorized or parallelized algorithm is equivalent to the specification we gave it.

But, there is a much more natural way to express this. Just say we want to perform a reduction operation on the array. In the STL, that’s `<valarray>`

``````#include <cstdlib> // for EXIT_SUCCESS
#include <iostream>
#include <valarray>

using std::cout, std::endl;

int main(void)
// Test driver for find_max.
{
const std::valarray array = {2, 6, 8, 23, 45, 43, 51, 62, 83, 78, 61, 18, 71, 34, 72};

cout << "HIGHEST: " << array.max() << endl;
return EXIT_SUCCESS;
}
``````

It is indeed a recursive function, but unfortunately it isn’t tail recursive, which means that you will have a call stack that is as deep as the array’s length, potentially causing a stack overflow if you try to find the maximum value in a large array. I would therefore not use a recursive function to find the maximum, and just use the iterative approach.

Your function has a bug; it doesn’t handle negative values correctly.

I would also simplify the structure of the function. First check if the end condition is met (`size == 1`), if so just return the single value. Otherwise, return the maximum of the first value and the result of the recursive call:

``````int find_max(const int array[], int size) {
if (size == 1)
return array[0];
else
return std::max(array[0], find_max(array + 1, size - 1));
}
``````

Since you are using C++, consider that you can turn your function into a template so it can work on any kind of array, not just arrays of `int`s. Even better would be to make it work for any kind of container, like `std::vector`, `std::list` and so on. Basically, try to implement `std::max_element()`; this should be a simple but good excercise of how to write generic code, which might help you in the future.