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;
}
