I'm trying to figure out how to write a cascade recursive function to find a max element in an integer array. I've tried to write some code but i think my function is more linear than cascade.
Here is my pascal code. vector = array of integer, l and r are used as indices, at first l = 0 and r = size of v - 1. I've tried to write this code without an auxiliary variable for maximum, however, i'm not sure if it is possible to do this task in a cascade way without such a variable.
function cascademax(v: vector; l, r: integer): integer;
begin
if r = 0 then
result := v[0]
else
begin
if (l < 0) or (r < 0) or (l > r) then
result := -1
else
begin
if l = r then
begin
if v[l] >= v[r] then
result := v[l]
else
result := v[r]
end
else
begin
if v[l] >= v[r] then
result := cascademax(v, l, r - 1)
else
result := cascademax(v, l + 1, r)
end;
end;
end;
end;
I will be glad if you write your code in any language or at least tell me if i need an auxiliary variable or not
You can visualize an array v
as if it were a binary tree (as depicted below):
l == r
, the element v[l]
(or v[r]
, since they are the same element) is the root of the tree (which is also a leaf);l < r
, for m = ⌊(l+r)/2⌋
, the element v[m]
is the root of the tree, the elements v[l..m-1]
form its left subtree and the elements v[m+1..r]
form its right subtree. l (m-1) m (m+1) r
+-----+-----+-----+-----+-----+-----+-----+
| | | | 501 | | | |
v: | | 723 | | | | 674 | |
| 440 | | 192 | | 346 | | 255 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
So you can solve the problem as follows:
#include <stdio.h>
int max(int x, int y) { return (x>y ? x : y); }
int c_max(int v[], int l, int r) {
if( l == r ) return v[l];
if( l+1 == r ) return max(v[l], v[r]);
return max(v[(l+r)/2], // element at the root of the tree
max(c_max(v, l, (l+r)/2 - 1), // maximum element in left subtree
c_max(v, (l+r)/2 + 1, r))); // maximum element in right subtree
}
int cascade_max(int v[], int n) {
// ensures that l and r are valid indices as long as n is valid!
return c_max(v, 0, n-1);
}
int main(void) {
int v[7] = {440, 723, 192, 501, 346, 674, 255};
printf("maximum element = %d\n", cascade_max(v, 7));
return 0;
}