Problems that are well-suited to recursion can be broken down into smaller, simpler subproblems. This is one of the things that gives recursion its power. When trying to use recursion to solve a problem, it usually seems best to try to break the problem down into simpler subproblems in finding your way to a solution.
You might notice that in finding the maximum value stored in an array, it is either the value of the first element, or the maximum value of the remaining elements. This breaks the problem into two parts: if the first element is larger than any remaining elements, you are done; otherwise, you must continue and see if the next element is larger than the remaining elements. In code, this might look like:
int max_in(size_t rest_sz, int *rest)
{
int curr_val = rest[0];
if (rest_sz == 1) {
return curr_val;
}
int max_in_rest = max_in(rest_sz-1, rest+1);
return curr_val > max_in_rest ? curr_val : max_in_rest;
}
Here, there is a base case: if rest_sz is 1, there is no need to look further; the value of first element (curr_val = rest[0]) is the maximum, and that value is returned. If the base case is not satisfied, execution of the function continues. max_in_rest is the result from the recursive function call max_in(rest_sz-1, rest+1). Here rest_sz-1 indicates the number of elements remaining in the portion of the array indicated by rest+1. In the new function call, the base case is met again, and eventually this case will be true since rest_sz is decremented with each recursive call. When that happens, the value of curr_val in the current stack frame will be returned; note that this value is the value of the last element in the array. Then, when the function returns to its caller, max_in_rest in that frame will get the returned value, after which the larger of curr_val or max_in_rest is returned to the previous caller, and so on, until finally control is returned to main().
Using pencil and paper to diagram each function call, the values of its variables, and what is returned would help to understand exactly how this recursion works.
You can apply the same method to solving the problem of finding the index of the maximum value of an array. In this case, if the value of the first element is greater than the value of any remaining elements, then the index of the maximum element is the index of the first element; otherwise the index of the maximum element is the index of the maximum value of the remaining elements. In code, this might look like:
size_t find_max_r(int arr[], int *rest, size_t rest_sz, size_t curr_ndx)
{
if (rest_sz == 1) {
return curr_ndx;
}
int curr_val = arr[curr_ndx];
size_t max_in_rest_ndx = find_max_r(arr, rest+1, rest_sz-1, curr_ndx+1);
int max_in_rest = arr[max_in_rest_ndx];
return curr_val >= max_in_rest ? curr_ndx : max_in_rest_ndx;
}
There is just a little more information to keep track of this time. Here, if the base case is satisfied, and rest_sz is 1, then there is no reason to look further, the current index curr_ndx is the index of the maximum value. Otherwise, find_max_r() is recursively called, with rest incremented to point to the remaining elements of the array, and rest_sz suitably decremented. This time, curr_ndx is keeping track of the current index with respect to the original array, and this value is passed into each function call; also, a pointer to the first element of the original array, arr, is passed into each function call so the index value curr_ndx can access the values from the original array.
Again, when the base case is reached, the current position in the array will be the end of the array, so the first elements to be compared in the return statement will be towards the end of the array, moving towards the front of the array. Note that >= is used here, instead of > so that the index of the first maximum value is returned; if you instead want the index of the last maximum value, simply change this to >.
Here is a complete program. Note the use of the helper function find_max() to call the recursive function find_max_r(), which allows the caller to use a function with the same signature that the posted code uses (except for the use of size_t types, which is really the correct type for array indices):
#include <stdio.h>
int max_in(size_t sz, int *rest);
size_t find_max(size_t sz, int arr[]);
size_t find_max_r(int arr[], int *rest, size_t rest_sz, size_t curr_ndx);
int main(void)
{
int array[] = { 2, 7, 1, 8, 2, 5, 1, 8 };
size_t array_sz = sizeof array / sizeof array[0];
int max_val = max_in(array_sz, array);
printf("Maximum value is: %d\n", max_val);
size_t max_ndx = find_max(array_sz, array);
printf("Maximum value index: %zu\n", max_ndx);
return 0;
}
int max_in(size_t rest_sz, int *rest)
{
int curr_val = rest[0];
if (rest_sz == 1) {
return curr_val;
}
int max_in_rest = max_in(rest_sz-1, rest+1);
return curr_val > max_in_rest ? curr_val : max_in_rest;
}
size_t find_max(size_t sz, int arr[])
{
int *rest = arr;
return find_max_r(arr, rest, sz, 0);
}
size_t find_max_r(int arr[], int *rest, size_t rest_sz, size_t curr_ndx)
{
if (rest_sz == 1) {
return curr_ndx;
}
int curr_val = arr[curr_ndx];
size_t max_in_rest_ndx = find_max_r(arr, rest+1, rest_sz-1, curr_ndx+1);
int max_in_rest = arr[max_in_rest_ndx];
return curr_val >= max_in_rest ? curr_ndx : max_in_rest_ndx;
}
Program output:
Maximum value is: 8
Maximum value index: 3
