使用递归查找数组中的最大值

Question

对于我被要求解决的问题之一，我使用 for 循环找到了数组的最大值，所以我尝试使用递归找到它，这就是我想出的：

 public static int findMax(int[] a, int head, int last) {

    int max = 0;
    if (head == last) {
        return a[head];
    } else if (a[head] < a[last]) {
        return findMax(a, head + 1, last);
    } else {
        return a[head];
    }
}

所以它工作正常并获得最大值，但我的问题是：对于基本情况返回 a[head] 以及当头部的值大于最后的值的情况是否可以？

原文由 Scarl 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您可以只用一个计数器轻松地做到这一点，这只是您这次要比较的值的索引：

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

这更好地显示了正在发生的事情，并使用默认的“递归”布局，例如使用公共基本步骤。初始调用是通过执行 findMax(a, a.length-1) 。

原文由 Joost 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

它实际上比那简单得多。基本情况是您是否已到达数组的末尾（下面三元控制块的“其他”部分）。否则，您将返回当前调用和递归调用的最大值。

 public static int findMax(int[] a) {
    return findMax(a, 0);
}
private static int findMax(int[] a, int i) {
    return i < a.length
           ? Math.max(a[i], findMax(a, i + 1))
           : Integer.MIN_VALUE;
}

在每个元素处，返回当前元素中较大的一个，以及具有更大索引的所有元素。 Integer.MIN_VALUE 将仅在空数组上返回。这在线性时间内运行。

原文由 azz 发布，翻译遵循 CC BY-SA 3.0 许可协议