我正在尝试为数据结构类编写一个 3 输入递归程序,用于最大值和最小值。我收到堆栈溢出错误。我无法判断我是否离开了阵列的末端,但我不应该像我的理解那样走得那么远。任何帮助将不胜感激。这是我的代码:
class Extrema {
// maxArray()
// returns the largest value in int array A
// p is position zero, r is position length-1
static int maxArray(int[] A, int p, int r) {
int q;
if (p == r) {
return A[p];
} else {
q = (p + r)/2;
return max(maxArray(A, p, q-1), maxArray(A, q+1, r));
}
}
// max()
// returns the largest value of two ints
private static int max(int a, int b) {
return a > b ? a : b;
}
// main()
public static void main(String[] args) {
int[] B = {-1, 2, 6, 3, 9, 2, -3, -2, 11, 5, 7};
System.out.println( "max = " + maxArray(B, 0, B.length-1) ); // output: max = 11
}
}
要么
做非递归,因为递归在这里真的没有任何意义:
static int maxArray(int[] A, int p, int r) {
int max = A[p];
for (int i = p + 1; i <= r; i++) {
if (A[i] > max)
max = A[i];
}
return max;
}
或者,如果您坚持某种递归,请使用仅稍作更改即可使用现有代码:
return max(maxArray(A, p, q), maxArray(A, q+1, r));
请注意,对第一个 maxArray 函数的调用现在传递q
,而不是作为结束索引q-1
传递。
更改此代码
if (p == r) {
return A[p];
}
自
if (p >= r) {
return A[p];
}
并注意,当您调用语句时
return max(maxArray(A, p, q-1), maxArray(A, q+1, r));
你丢失了Q元素,所以调用
return max(maxArray(A, p, q), maxArray(A, q+1, r));