Finding Maximum Value In Array Recursively

March 27, 2024 Post a Comment

I am trying to use recursion to find the maximum value in an array in JavaScript. I created the function, but cannot figure out how to do it recursively. function Max(a) { var a

Solution 1:

Here is an example of a recursive function that takes an array of numbers and compares the first two, removes the lesser, and then calls itself again on the given array minus the removed number.

functionmax(numArray) 
{
    // copy the given array 
    nums = numArray.slice();

    // base case: if we're at the last number, return itif (nums.length == 1) { return nums[0]; }

    // check the first two numbers in the array and remove the lesserif (nums[0] < nums[1]) { nums.splice(0,1); }
    else { nums.splice(1,1); }

    // with one less number in the array, call the same functionreturnmax(nums);
}

Here's a jsfiddle: https://jsfiddle.net/t3q5sm1g/1/

Solution 2:

let max = (list) => {

  // Returns first number if list length is 1if (list.length === 1) return list[0]

  // Returns the greater number between the first 2 numbers in an arrayif (list.length === 2) return (list[0] > list[1]) ? list[0] : list[1]

  // If array length is 3+ (Read Below)const subMax = max(list.slice(1));
  return (list[0] > subMax) ? list[0] : subMax;
}

// Example
max([5,5,5,8,6,7,4,7])

It is important to understand how the 'Call Stack' works for recursions.

In the example above, since the array length is over 3 the first line to be called is the

const subMax = max(list.slice(1));

All this line does is take out the first item in the array and recalls the function with the shorter array as its argument. This continues until the arrays length is 2 then returns the greater of the 2. Then the function can complete all its previous partially completed states.

Solution 3:

functionmax(array) {
  if (array.length === 1) {  // Step1: set up your base casereturnarray[0]
 } else {  
     return Math.max(array.shift(), max(array); // Step2: rec case
 }
}

Each time the recursive case is called it gets it closer to the base case.

Math.max accepts two numbers, then compares them, then returns the higher out of the two.

Each time you call array.shift() you are popping off the first element in the array from the array, so the second argument in the recursive call is the array shortened by one.

When array.length is down to just one element, return that element and watch the stack unfold.

Solution 4:

This is actually one of the questions I’ve asked candidates to a software position: Find the maximum number in a jagged array. Each element of the array can be a number or an array of other numbers on indefinite number of levels, like this:

var ar = [2, 4, 10, [12, 4, [100, 99], 4], [3, 2, 99], 0];

And now, just for fun and to keep this post short, I will include two solutions to the question. The first solution uses recursion while the second solution uses a stack. As a matter of fact all these problems with recursion can be also solved by using the stack approach.

Solution I: Find maximum using recursion

// Use recursion to find the maximum numeric value in an array of arraysfunctionfindMax1(ar)
{
    var max = -Infinity;

    // Cycle through all the elements of the arrayfor(var i = 0; i < ar.length; i++)
    {
        var el = ar[i];

        // If an element is of type array then invoke the same function// to find out the maximum element of that subarrayif ( Array.isArray(el) )
        {
            el = findMax1( el );
        }

        if ( el > max )
        {
            max = el;
        }
    }

    return max;
}

Solution II: Find maximum using a stack

// Use a stack to find the maximum numeric value in an array of arraysfunctionfindMax2(arElements)
{
    var max = -Infinity;

    // This is the stack on which will put the first array and then // all the other sub-arrays that we find as we traverse an array     var arrays = [];

    arrays.push(arElements);

    // Loop as long as are arrays added to the stack for processingwhile(arrays.length > 0)
    {
        // Extract an array from the stack
        ar = arrays.pop();

        // ... and loop through its elementsfor(var i = 0; i < ar.length; i++)
        {
            var el = ar[i];

            // If an element is of type array, we'll add it to stack// to be processed laterif ( Array.isArray(el) )
            {
                arrays.push(el);
                continue;
            }

            if ( el > max )
            {
                max = el;
            }
        }
    }

    return max;
}

Feel free to optimize the above code. You can also find this code as a gist on github.

Solution 5:

ES6 syntax makes this really concise.

const findMax = arr => {
  if (!Array.isArray(arr)) throw 'Not an array'if (arr.length === 0) return undefined
  const [head, ...tail] = arr
  if (arr.length === 1) returnheadreturnhead > findMax(tail) 
    ? head
    : findMax(tail)
}

javascript magazin