Return语句不能正确终止递归方法

Question

我有一个方法getNextPrime（int num），它应该在该方法接收的值之后识别最接近的质数。

如果num是偶数，它将递增它并再次调用自己。如果它是奇数，它将运行一个for循环来检查它是否可以被3和num的一半值之间的奇数整除。如果是，那么它将把num增加2，方法将再次调用自己，否则它将返回新的num值，这是一个质数。

问题是，当程序到达return语句时，它将跳转到if语句并返回num 1的原始值。我调试这个已经有一段时间了，但它毫无意义。无论我在哪里放置return语句，该方法都会跳转到if语句，而不是终止该方法并将值返回到调用它的位置。

public int getNextPrime(int num){

    if(num % 2 == 0){
        //even numbers are not prime

        getNextPrime(++num);
    }
    else{

        for(int i = 3; i < (num + 1) / 2; i += 2){

            if(num % i == 0) {
                getNextPrime(num += 2); //consider odd numbers only
            }
        }
    }

    return num; //jumps to if and terminates
}

但是，如果我将else语句更改为单独的if语句，if（num%2！=0）将正常工作。

为什么会发生这种情况？

*注：该方法给出的值大于3，1、2和3是素数这一事实无关紧要。

Answer 1

你的返回语句工作正常，但是...你把1,2和3留在了你的逻辑之外。2是偶数，1不是质数。

Answer 2

当我们用参数8调用你的函数时，让我们试着看看调用堆栈；

第一个调用是：GetNextTime（8）。由于数字是偶数，该函数进入if部分，并使用GetNextTime（9）再次调用自身。这一次，else部分开始，检查for循环中的可整除性，发现9是可整除的，所以调用getNextTime（11）。现在GetNextTime（11）再次执行else和for循环，发现11是prime，并将数字11返回给调用者，但如果仔细观察，就不会将该值存储在变量中，GetNextTime调用中的num变量是9，当GetNextTime（9）返回该值时，它会将该值返回给GetNextTime（8）。在GetNextTime（8）中，也没有真正存储从递归调用堆栈返回的num变量。您只需返回该函数中定义的num变量，在调用GetNextTime（11）之前，该变量恰好递增，因此该值为9，并返回9。

下面给出了带有相同if-else块的修正程序，供您参考。

public static int genNextPrime(int num) {
    if (num % 2 == 0) {
        num = genNextPrime(++num);
    } else {
        for (int i = 3; i < (num + 1) / 2; i += 2) {
            if (num % i == 0) {
                num += 2;
                num = genNextPrime(num);
            }
        }
    }
    return num;
}

Answer 3

这里只有一个结构性问题。到达单个返回不会折叠整个调用堆栈，它只返回到以前的调用。

您需要保存每次调用GetNextTime（）的结果，并将其用作返回值，以便实际找到的值沿着调用链传回，并返回给初始调用方。目前，您只返回传入的数字，因为您从未修改它。

修复是一个非常简单的修改。你在哪里

getNextPrime(++num);

... and ...

getNextPrime(num+2);

换成

return getNextPrime(++num);

... and ...

return getNextPrime(num+2);

你选择的算法的问题是效率低下。你只需要使用较小的素数来测试整除性，而不是所有的奇数，并且只能测试原始数的平方根。

实现只是一个练习。