C语言 - 递归打印质数列表

Question

我在学校的C编程作业中遇到了一些问题。我需要使用递归返回给定范围内的质数。

目前为止我写的代码如下：

#include <stdio.h>
#include <stdlib.h>

int primeNumberList(int n, int m, int z);

int main() {
    int n1 = 0,
        n2 = 10,
        d = 2;

    printf("n1 = %d | n2 = %d | d = %d\n\n", n1, n2, d);    
    printf("Prime Numbers between %d and %d are: \n", n1, n2);

    primeNumberList(n1, n2, d);

    printf("\n\n");

    return 0;
}

int primeNumberList(int n, int m, int z) {
    int notPrime = 0;

    if (n <= 1) {
        primeNumberList(n + 1, m, z);
    } else
    if (n < m) {
        if (z <= n / 2) {
            if (n % z == 0) {
                notPrime = 1;
                z = 2;
            } else {
                primeNumberList(n, m, z + 1);
            }
        }
        if (notPrime == 0) {
            printf("%d ", n);
        }
        primeNumberList(n + 1, m, z);
    }
}

当我运行这个程序时，它会在处理到限制（在函数中是m（在main中为n2））之前的所有数字后，不会停止递归，而是以某种方式从n中减去数字，并开始打印一些不是质数的其他数字。 当我在调试模式下运行它时，它似乎在最后循环，但没有任何东西可以循环...我尝试添加一个return 0;甚至是一个带有一些文本的printf，但它完全忽略了它。 有人能看出我做错了什么吗？为什么它在n < m时不会停止？

- Christoffer

---

“primeNumberList” 没有 “return” 语句？ - Fantastic Mr Fox

if(z <= n/2) 块下的缩进是平的。 - emery

@Ben：如果你是指使用“return 0;”或“return;”也不起作用，那么这并不是解决办法。难道你是想说，应该将值分配给一个变量，然后返回该变量吗？ - Christoffer

@Christoffer，你每次调用可能会有两个递归调用的潜力，这是我认为导致问题的原因。目前，将if(n == m-1) exit(1);添加到primeNumberList开头是一个可行的但不太正规的解决方案。 - River

@River：非常感谢，它的作用就像应该的那样！你提到这是一个hacky解决方案，这是否意味着通常不应该使用它，还是只是因为我的编码有点混乱，因此使用它比替代方案更容易？ - Christoffer

@Christoffer 我为你找到了一个真正的解决方案（在下面发布为答案）。 "Hacky" 只是意味着它通常是不好的编码实践，不应该使用。强制退出永远都不应该是递归结束的方式，这只是一种不好的做法。 - River

Answer 1

我发现了你的问题。每次调用primeNumberList时，你都有可能进行两次递归调用。

在内部最深层的else中，当你从primeNumberList(n, m, z+1);返回后，你仍然可以继续打印一个质数并调用primeNumberList(n+1, m, z);。这不是你想要的行为，你想要直接在这个内部的else调用之后返回。

所以，只需在每次调用primeNumberList之前添加return（primeNumberList(x);变成return primeNumberList(x);），并在此函数末尾添加return 0（这最后一个return只是为了让编译器高兴）。

- River

Answer 2

尝试使用更简洁的方式：定义一个单独的isPrime函数并调用它。

http://www.cquestions.com/2011/08/prime-number-program-in-c-using.html

int isPrime(int num,int i){

  if(i==1){
      return 1;
  }else{
     if(num%i==0)
       return 0;
     else
       isPrime(num,i-1);
  }
}

- emery

Answer 3

你的递归函数退出条件不正确。

当你调用递归函数时，它会升起然后下降。当我逐步运行你的代码时，在它升起的同时，我得到了完整的质数列表，如下所示： 然后随着它的继续，以下数字被打印出来：
你的问题: 为什么当 n < m 时它不停止？
因为在开始回溯时，存储在值n中的值也会逐渐通过已调用的递归迭代向下回溯，从而使执行流保持在循环中。 此外，如果回溯将执行流带到超过printf("%d ", n);语句的点，则n的值，无论在该回溯迭代中是什么，都将被打印出来。

一个离开而不打印任何超过n == 10的东西的方法是创建一个旁路变量，并将其用作打印标准：

static done = 0;  

当您不想再打印任何值时，请将done设置为1，因为它正在解开。

这是一个修改后的函数:

int primeNumberList(int n, int m, int z) {
    int notPrime = 0;
    static done = 0;//add a bypass variable, init to zero

    if (n <= 1) {
        primeNumberList(n + 1, m, z);
    } 
    else
    {
        if(n == 10)
            {
                done = 1; //at this point all primes (except 1) are printed
                          //so set done to 1
            }
        if (n < m) 
        {
            if (z <= n / 2) 
            {
                if (n % z == 0) 
                {
                    notPrime = 1;
                    z = 2;
                } 
                else 
                {
                    primeNumberList(n, m, z + 1);
                }
            }
            if ((notPrime == 0) && (!done)) //test done before printing
            {
                printf("%d ", n);
            }
            primeNumberList(n + 1, m, z);
        }
    }
    return 0;//add this return statement
}

- ryyker