java - 为什么我会收到 Stackoverflow 错误？

Question

我有一个应该猜测数字的小递归算法。我调用方法 guessNumber 并给出一个数字和一个比该数字低的值和一个比该数字高的值。如果该值高于数字区域的中间值，则对新的数字区域进行相同的处理。但它的值(value)较低，它与较低的数字区域相同。如果这些情况都不成立，那么它会返回最大值(它可能是最小值，因为此时它们是相同的)。但是为什么给它一个 StackOverflowError 呢？我不明白为什么程序无法结束。任何帮助将不胜感激。谢谢。

public class Starter {

/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
    Starter s = new Starter();
    System.out.println(s.guessNumber(18, 1, 100));
}

public int guessNumber(int num, int min, int max) {
    int middle = (max - (min - 1)) / 2;
    if (num > middle) {
        guessNumber(num, middle + 1, max);
    } else if (num < middle) {
        guessNumber(num, min, middle);
    }
    return max;
}
}

现在我不再收到此代码的错误:

public int guessNumber(int num, int min, int max) {
int middle = (max + min) / 2;
if (num > middle) {
    return guessNumber(num, middle + 1, max);
} else if (num < middle) {
    return guessNumber(num, min, middle);
}
return max;
}

但数字不正确。如果我这样调用它 guessNumber(18, 1, 100) 预期输出应该是 18 但我得到 19。如果我这样称呼 guessNumber(34, 1, 100) 那么输出就是 37

Answer 1

首先，你忘了返回递归调用的值。

其次，您对middle 的计算是错误的。例如，如果 min 为 10 而 max 为 20，则您的计算会将 5 分配给 middle，而不是 15。

public int guessNumber(int num, int min, int max) {
    if (min == max) {
        return min;
    }
    int middle = (max + min) / 2;
    if (num > middle) {
        return guessNumber(num, middle + 1, max);
    } else {
        return guessNumber(num, min, middle);
    }
}