Find the max of a vector recursive

Hello all,

Im trying to find the max value of an element in a vector, for learning purposes Ineed to do this recursive. I have been trying this all over again but something goes terribly worng. Could anybody point out to me what I am doing wrong? Thanks in advance.

function output = recursive_max(input)
%%Write a function called recursive_max that finds the maximum element in a
%%vector. You are not allowed to use loops or any built-in functions other
%%than length. The sole output argument is the maximum value in the input
%%vector. Hint: the maximum value of a vector is the larger of its first
%%element and the maximum of the rest of the elements.

l = length(input);

if l == 1
    output = recursive_max(input(end))
else
    
    if input(end-1) >= input(end)
       input(end) = [];
       recursive_max(input);
    end    
   input(end-1) = []    
end

end

Answer 1

[John D'Errico]

This is a godawful problem to solve using recursive coding. Why? Suppose your vector has a million elements in it. Then this code will need to make 1 MILLION nested, recursive calls. That will be 1 MILLION separate function workspaces, all of which will be actiuve until the final call allows all of those recursive calls to unwind. 1 MILLION calls. Can you possibly want to do that? NO! Not in a million years.

Yes, I understand this is homework, and you need to do as directed. What I want you to understand is why that is such a bad idea for when you start writing code of your own.

Regardless, you made a (barely) credible start to your task, though your code is not really that close to being workable. What did you do wrong?

A recursive code will need to have an end condition. Your code has that, to deal with the problem when your vector has length 1. For longer vectors, You will compare the first element to recursive_max of the rest.

By the way, not needing to use other built-in functions means you cannot use max, but it also means you cannot even use the > comparison operator. That is in fact a built-in function. Anyway, your code should look most simply like that below:

x = [1 3 2 5 6 2];
recursive_max(x)

ans = 6

function output = recursive_max(input)
  if length(input) == 1
    output = input;
  else
    output = recursive_max(input(2:end));
    if input(1) > output
      output = input(1);
    end
  end
end

So think about it. Will this work? Of course. Do you want to use that code in any rational form? YE GOD NO!

[Raymond Gilbers]

Thanks John,

I appreciate your help. Although I think I understand what you have done. after the Else you give Output the vector input from 2 till end. and compare it with the first element input(1) if this is true output gets this value. It keeps doing this untill all elements are checked due to the statement recursive_max(input(2:end))

I get your point this would take up lots of memory when you use a huge vector. The main point of this exercise is to understand the recursive part of it. But it is tricky I think I understand your code but I would never come up with it.

Again thanks a lot

[Aditya]

may be using the isscalar function will be better in case of using the length

Answer 2

[Syed Muhammad Anas Ibrahim]

Another compact solution can be as follows:

Thanks for carefull watch in code. Hope it could address nan issue as well

function val = maxi_func(n)
len = length(n);
if len==1
    val = n(len);
elseif len==2
    val = n(2);
    if n(1)>n(2)||isnan(n(1))
        val = n(1);
    end
else
    val = maxi_func(n(1:len-1));
    if n(len)>val||isnan(n(len))
        val = n(len);
    end
end
end

[Walter Roberson]

That code can fail if there are inf or -inf .

Suppose the input is [inf inf] . Then

val = n(1)*(n(1)>n(2))+n(2)*(n(1)<n(2));

will be

val = inf*(inf>inf)+inf*(inf<inf);

The inf>inf part and the inf<inf part both yield 0. inf*0 is nan. So you would have inf*0+inf*0 which would be nan+nan which would yield nan.

The code also can fail if there are two identical finite values. Suppose the input is [3 3]. Then

val = n(1)*(n(1)>n(2))+n(2)*(n(1)<n(2));

would be

val = 3*(3>3)+3*(3<3);

The 3>3 part and the 3<3 part are both false, value 0, So it would be

val = 3*0 + 3*0

which is going to give 0. In this case of identical all-finite values, the val that is output is going to be 0 instead of the value.

The code has infinite recursion in the case that the input vector is a scalar.

[Walter Roberson]

The adjusted code acts a bit oddly on NaN.

elseif len==2
    val = n(2);
    if n(1)>n(2)
        val = n(1);
    end

Suppose n(1) is nan and n(2) is finite. Then n(1)>n(2) is false and val=n(2) is still in effect, so you return the finite value.

Suppose n(1) is finite and n(2) is nan. Then n(1)>n(2) is false and val=n(2) is still in effect, so you return the nan.

Your code should handle nan consistently. Either it should ignore all nan and return the maximum of the finite elements, or else it should return nan if there is any nan. Whether it returns nan or not should not be up to the chance permutation of the elements.