以递归方式查找数组中的最大值

Question

我试图使用递归来在JavaScript中找到数组中的最大值。我创建了该函数，但无法弄清楚如何递归执行。

function Max(a) {
  var a = [2,3,5];
  return Math.max.apply(Math, a);
}

Answer 1

下面是一个递归函数的示例，它接受一个数字数组并比较前两个，删除较小的数字，然后在给定数组上再次调用自身减去删除的数字。

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

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

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

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

这是一个jsfiddle：https://jsfiddle.net/t3q5sm1g/1/

Answer 2

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

每次调用递归的情况时，它都会更接近基本情况。

Math.max接受两个数字，然后比较它们，然后从两个数字中返回更高的数字。

每次调用array.shift（）时，都会从数组中弹出数组中的第一个元素，因此递归调用中的第二个参数是缩短为1的数组。

当array.length只有一个元素时，返回该元素并观察堆栈展开。

Answer 3

这实际上是我向候选人询问软件位置的问题之一：找到锯齿状阵列中的最大数量。数组的每个元素可以是无限数量级别的数字或其他数字的数组，如下所示：

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

而现在，只是为了好玩并保持这篇文章的简短，我将在这个问题中加入两个解决方案。第一种解决方案使用递归，而第二种解决方案使用堆栈。事实上，所有这些递归问题也可以通过使用堆栈方法来解决。

Solution I: Find maximum using recursion

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

    // Cycle through all the elements of the array
    for(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 subarray
        if ( 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 arrays
function findMax2(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 processing
    while(arrays.length > 0)
    {
        // Extract an array from the stack
        ar = arrays.pop();

        // ... and loop through its elements
        for(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 later
            if ( Array.isArray(el) )
            {
                arrays.push(el);
                continue;
            }

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

    return max;
}

随意优化上面的代码。你也可以找到这个代码作为gist on github。

Answer 4

let max = (list) => {

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

  // Returns the greater number between the first 2 numbers in an array
  if (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])

了解“调用堆栈”如何用于递归非常重要。

在上面的例子中，由于数组长度超过3，所以要调用的第一行是

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

所有这一行都取出了数组中的第一项，并以较短的数组作为参数调用函数。这一直持续到数组长度为2然后返回2中的较大者。然后该函数可以完成其先前部分完成的所有状态。

Answer 5

ES6语法使这非常简洁。

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) return head
  return head > findMax(tail) 
    ? head
    : findMax(tail)
}

Answer 6

试试这个：

const biggestElement = list => {
    if (list.length == 1)
        return list[0];
    if (list[0] > list[1])
        list[1] = list[0];
    list = list.splice(1);
    return biggestElement(list);
}