Find the maximum element of an array recursively
I have this function:
int max(int arr[], int size)
{
size--;
if(size > 0)
{
int max = max(arr, size);
if(arr[max] > arr[size]) return max;
}
return size;
}
And of course it works. My question is, how does it work? Can anyone explain this to me step by step? It's Saturday, so maybe someone has some time: D I especially mean those two lines in the block.
source to share
The code looks like this:
1 int max(int arr[], int size){
2 size--;
3 if(size > 0){
4 int max = max(arr, size);
5 if(arr[max] > arr[size]) return max;
6 }
7 return size;
8 }
You call it by passing in its array and the size (or length) of that array.
The first important point of code hitting is line 4 when it calls itself recursively. But notice that on line 2, the size has been reduced by one. Therefore, you can think of size as an index referencing an array element that is being considered by the current function call.
This means that eventually the size of the array will be zero, and we will consider the first element of the array. At this point, lines 3 through 6 are skipped and 0 is returned.
When one of the recursive calls returns, we are back at line 4.
For the first return, this means that int max = 0;
.
Now we are comparing the zero element with the first element. We return the index whichever is greater. The next comparison will be between the second element and whichever is the larger of the first two.
This continues until all recursive calls have returned, after which the index of the largest element is returned to the calling function.
Note what return size;
should be replaced with return 0
to increase legibility.
source to share
Let's take this array for example:
int arr[] = { 42, 54, 23 };
max(arr, 3);
This function works by checking the maximum current of the current element against the maximum of all previous elements. Here is a view of the stack calls:
max(arr, 3)
max(arr, 2)
max(arr, 1)
return 0
arr[0] (arr[max] = 42) <= arr[0] (arr[size] = 42) => return size (0)
arr[0] (arr[max] = 42) <= arr[1] (arr[size] = 54) => return size (1)
arr[1] (arr[max] = 54) > arr[2] (arr[size] = 23) => return max (1)
NB: It's a bad idea to name both the variable and the function with the same identifier.
source to share
Let's look at the problem for arr[] = [1,2]
what the challenge meansmax(arr[], 2)
size--; // 2-1 = 1
if(size > 0) //True
{
int max = max(arr, size); //Going into the recursive call
This is a recursive run:
size--; // Now 1-1 = 0
if(size > 0) //False
return size; //0 returned
Now, back to the calling function:
int max = 0 //From return
if(arr[max] > arr[size]) //arr[0]>arr[1] which is false
}
return size; //Now, control reaches here and 1 is passed back to the calling scope
}
source to share
