recursionmaxpascal

Cascade recursion - max element in array


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


Solution

  • You can visualize an array v as if it were a binary tree (as depicted below):

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