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

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];
    }
}

所以它工作正常并获得最大值,但我的问题是:是否可以为基本情况返回[head]并且对于头部的值是>最后值的情况？

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).

Answer 2

它实际上要简单得多.基本情况是你到达了数组的末尾(下面的三元控制块的'else'部分).否则,返回当前和递归调用的最大值.

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将仅在空数组上返回.这在线性时间内运行.