C - 打印素数列表（递归）

Question

我在学校的 C 编程作业中遇到了一些问题。我应该 return 给定范围内的素数，并且必须使用递归来完成。

到目前为止我得到的代码是这样的：

#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（n2在main)) 它不会破坏递归，但会以某种方式设法从 n 中减去数字，并开始打印其他一些不是素数的数字。当我在调试中运行它时，它似乎在最后循环，但没有什么可循环的……我试过添加一个 return 0; 甚至 printf 一些文本，但它完全忽略它。

谁能看出我在这里做错了什么？为什么在 n < m 时不停止？

Answer 1

我发现了你的问题。每次调用 primeNumberList.

时，您都有可能进行两次递归调用

在你从 primeNumberList(n, m, z+1); return 之后（在最里面的 else 下）你仍然可以继续打印素数并调用 primeNumberList(n+1, m, z);。这不是您想要的行为，您希望在此内部 else 调用之后直接 return。

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

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

Answer 3

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

当你调用递归函数时，它先结束，然后结束。当我运行你的代码一步步通过时，随着向上，我得到了完整的素数列表，如下：

然后继续打印以下数字：

你的问题：为什么当 n < m 时它不停止？
因为当您开始展开时，存储在值 n 中的值也会通过已调用的递归迭代开始展开，从而允许执行流程留在循环中。此外，如果 unwind 将执行流带到通过 printf("%d ", n); 语句的点，则 n 的值，无论它在 unwind 迭代中是什么，都将是打印出来。

离开时不打印超出 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
}

C - 打印素数列表（递归）

C - Print list of Prime Numbers (recursion)

c

recursion

primes

if-statement