Finding Max Value in an Array Using Recursion

Finding Max value in an array using recursion

You could just as easily do it with only one counter, just the index of the value you want to compare this time:

public static int findMax(int[] a, int index) {
    if (index > 0) {
        return Math.max(a[index], findMax(a, index-1))
    } else {
        return a[0];
    }
}

This much better shows what is going on, and uses the default "recursion" layout, e.g. with a common base step. Initial call is by doing findMax(a, a.length-1).

How to use recursion to implement "Finding the maximum value in an array" in Python?

If you want to use recursion, it's very important to define carefully the end cases.

The maximum of the elements of a list is, obviously, either the first element or the maximum of the rest of the list: it's the greatest of the two values. That's actually the recursion you are looking for.

But what happens when there is no first element? You have an empty list, and an undefined behaviour. Why not maximum([]) = 0? Because it would lead to some inconsistency: maximum([-1]) = greatest(-1, maximum([])) = greatest(-1, 0) = 0. (You could also try maximum([]) == -math.inf, but this won't be very intuitive!)

What if the rest of the list is empty? No problem, you have just one element and it is the maximum.

Just translate this analysis into code:

def maximum(xs):
    if len(xs) == 0:
        raise ValueError()
    elif len(xs) == 1:
        return xs[0]
    else:
        u = xs[0]
        v = maximum(xs[1:])
        return u if u >= v else v # greatest(u, v)

More on maximum([])

I will try to give a value to maximum([]). I repeat the argument above. For any given n, maximum([n]) = greatest(n, maximum([])) = n. This implies that, for every n, maximum([]) <= n. The only value that meets this condition is -math.inf. Why not define maximum([]) == -math.inf? Imagine you create a minimum function. For symetrical reasons, you will have to define minimum([]) == math.inf. Hence it exists a list l0 = [] such that minimum(l0) > maximum(l0). No one would accept such a possibility.

What should we do now? There are two main possibilities: defensive programming or use a contract. In defensive programming, the function will check the arguments it has received, and fail if one of these arguments is not correct. That's what I did:

def maximum(xs):
    if len(xs) == 0:
           raise ValueError()
    ...

If you use a contract, you will basically say: if you give this function an empty list, then the behaviour is undefined. It might return any value, crash, loop forever, .... Here, you would have something like:

def maximum(xs):
    """!!! xs must not be empty !!!"""
    ...

It seems the same, but there is a huge difference. You can use, for implementation reasons, -math.inf as the return value for maximum([]), because it is now clear that it doesn't have any meaning. Someone who tries to check if minimum(l0) <= maximum(l0) for l0 = [] clearly breaks the contract and won't be surprised by the result. Of course, if you want to make it robust, you will write:

def maximum(xs):
    """PRECONDITION: xs must not be empty"""
    assert len(xs) != 0 # can be disabled at runtime at your own risks
    _maximum(xs)

def _maximum(xs):
    """no precondition here"""
    if len(xs) == 0:
        return -math.inf
    else:
        u = xs[0]
        v = _maximum(xs[1:])
        return u if u >= v else v # greatest(u, v)

How to find Max in an Array using Recursion and dividing in half?

You are severely overthinking this problem. The process of finding the max recursively by divide-and-conquer strategy is embarrassingly simple:

• If there's nothing to divide because the range has a single item, return the item
• Otherwise divide the range in two, call for max on both halves, and return the larger of the two

Here is how it looks in code:

int maxarray(const int a[], int first, int last) {
    // Single-item range
    if (first+1 == last) {
        return a[first];
    }
    // Divide-and-conquer
    int mid = first + (last - first) / 2;
    int leftMax = maxarray(a, first, mid);
    int rightMax = maxarray(a, mid, last);
    return leftMax > rightMax ? leftMax : rightMax;
}

Demo.

Note that despite the fact that we divide the range, the algorithm is still linear, because we solve both sub-problems in all cases. Another way to put it is that we must look at every single item in the range, regardless of the order.

Finding largest value in array using recursion

I would recommend you use a helper function that calls your largestvalue function like so:

int largestValue(int arr[], int size){
    int middle = (size - 1)/2;
    int first_max = largestValue(arr, 0, middle);
    int second_max = largestValue(arr, middle + 1, largest - 1);
    if(first_max < second_max){
       return second_max;
    }
    return first_max;
}

Finding max value in array using recursion in PHP

The problem is because of your base condition here,

if($arr = []){ ...

= is an assignment operator, not comparison operator. What you need here is a comparison operator ==. So it should be,

if($arr == []){

Furthermore, you can change your base condition like this way,

if(count($arr) == 1){
    return $arr[0]; // base case
}

So your find_max() function should be like this:

function find_max($arr){
    if(count($arr) == 1){
        return $arr[0]; // base case
    }
    if ($arr[0] > find_max(rest_of($arr))){
        return $arr[0];
    } else{
        return find_max(rest_of($arr));
    }
}

---

Related Topics