Cascade recursion - max element in array

Question

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

Answer 1

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

• when 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);
• when 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;
}

Answer 2

Recursion really isn't necessary to solve this, but if you insist on using it for pedagogical reasons, it's also not difficult. For any recursive function you need:

• At least one base case where the function returns rather than recursively calling itself.
• At least one case where the function calls itself recursively, updating the parameters/arguments to converge on one of the base cases.

program Test;
const
  max_dim = 10;

type
  arr = array [1..max_dim] of integer;

var
  a : arr = (2, 3, 8, -1, 0, 9, 11, 3, 4, 5);

  function casc_max(a : arr; cur_idx : integer; max : integer) : integer;
  begin
    if cur_idx > max_dim then
      casc_max := max
    else if a[cur_idx] > max then
      casc_max := casc_max(a, cur_idx + 1, a[cur_idx])
    else
      casc_max := casc_max(a, cur_idx + 1, max)
  end;

begin
  writeln(casc_max(a, 1, a[1]));

end.

$ fpc test.pas
Free Pascal Compiler version 3.0.4+dfsg-18ubuntu2 [2018/08/29] for x86_64
Copyright (c) 1993-2017 by Florian Klaempfl and others
Target OS: Linux for x86-64
Compiling test.pas
Linking test
/usr/bin/ld.bfd: warning: link.res contains output sections; did you forget -T?
24 lines compiled, 0.1 sec
$ ./test
11