0
\$\begingroup\$

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;
}
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Please choose your language. C answers will be very different from C++. On a side note, this looks more like C. \$\endgroup\$ Mar 5, 2022 at 19:28

2 Answers 2

1
\$\begingroup\$

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;
}
\$\endgroup\$
1
  • \$\begingroup\$ thank you again. It has been very helpful. I'm also taking note of the things I have to keep in mind. I really appreciate it. \$\endgroup\$ Mar 8, 2022 at 17:24
1
\$\begingroup\$

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 ints. 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.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you! I still don't know much about vectors. (I haven't been taught it in class yet). I'll take a look at that too: std::max_element(); \$\endgroup\$ Mar 6, 2022 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.