递归寻找主要因素

Question

我开始自学 C 并尝试构建一组有用的函数和程序以供将来参考。如果相关，这是 C99。

这是我最近的程序迭代。在输出端，我想得到数字 n 的质因数分解。然而，我得到了所有因素的列表，没有重复的因素。我包含了一些打印语句来尝试调试，发现错误与递归有关，但无法弄清楚如何进一步解释它。我以前尝试制作 int 类型的递归函数，但很难让它与数组 p 一起工作。

n 是我要分解的数字
p是一个数组，用于存储找到的素数
j 是 p
c 是我作为 n

我知道可能有更有效的方法来声明 p 以节省内存，但由于这主要是为了参考，内存不是一个大问题。

我发现了这些问题，但认为它们没有回答我的问题

finding greatest prime factor using recursion in c :这个问题是关于崩溃代码的。我的编译、运行并产生合理合理的输出，我只是想知道为什么输出不是我所期望的。
is there ever a time you would not use recursion? [closed] ：这表明递归不是质因数分解的好选择-我不知道，但怀疑这也适用于 C。因为这是供参考，我不知道认为这是一个巨大的问题。如果您不同意，请说明原因。

我的主要问题是：为什么输出显示 n 的所有因子？为什么它不重复主要因素？我该怎么做才能修复它？

  #include <stdio.h>

  #define NELEMS(x)  (sizeof(x) / sizeof((x)[0]))

  void factors(int n, int p[], int j) {
  /// if n is divisible by c, store c, and continue with n/c
      int c;
      for (c=2; c < n; c++) {
          if (c > n) break;
          if (n%c == 0) {
              p[j] = c;
              printf("%d has been added to p \t", c);
              printf("n has been reduced to %d \t", n/c);
              printf("j is %d \n", j);
              j++;
              if (n == c) break;
              factors(n/c, p, j);
          }
      }
  }

  int main() {
      /// set up number to factor, and array to hold factors
      int n = 24;
      int p[n/2];
      int i=0;
      for (i=0; i<NELEMS(p); i++) {
          p[i]=0;
      }

      int j = 0;
      factors(n, p, j);

      printf("the prime factors of %d are:\n",n);
      for (i=0; i<NELEMS(p); i++) {
          printf("%d \n", p[i]);
      }

  }

Answer 1

来自This answer：

why does recursion cause Whosebug so much more than loops do

因为每次递归调用都会用到栈上的一些space。如果你的递归太深，那么它会导致 Whosebug，这取决于堆栈中允许的最大深度。

使用递归时，您应该非常小心并确保提供基本情况。递归中的基本情况是递归结束和堆栈开始展开的条件。这是递归导致 Whosebug 错误的主要原因。如果找不到任何基本情况，它将进入无限递归，这肯定会导致错误，因为 Stack 是有限的。

-

看来您的 for 挡住了路，c 将递增，并且不会再次检查相同的值。

例如，如果输入是 8，我们想要 (2,2,2) 而不是 (2,4)。

我建议将您的 if (c%n ==0) 替换为 while，不要忘记在此期间替换 n 的值，您不想在其中循环。

这似乎是个不错的答案：

int primes(int nbr, int cur)
{
  if (cur > nbr)
    return (0);
  else
    {
      if (nbr % cur == 0 && isprime(cur) == 1)
        {
          printf("%d\n", cur);
          return (primes(nbr / cur, 2));
        }
      return (primes(nbr, cur + 1));
    }
}

在您的 main

中使用 cur = 2 调用该函数

Answer 2

编辑我突然想到 n 的最小因子一定是质数，所以我相应地编辑了答案。

Why does the output show all factors of n?

因为你测试 c 是否是 n 的因数并将它添加到数组 p 中，无论 c 是否为质数。然后你继续测试c以上的数字，甚至是c的倍数。

Why does it not repeat the prime factors?

因为当您找到作为因数的数字 c 时，您不一定要检查它以确定它本身是否是复合数。

将c添加到p后，需要在(n / c)上递归调用factor，然后停止。

这里大致是你需要的（但没有测试甚至编译）

int factorise(int n, int p[], int j)
{
    int factorsFound = 0;

    for (c = 2 ; c * c <= n && factorsFound == 0 ; ++ c)
    {
        if (n % c == 0)
        {
            p[j] = c;
            factorsFound = factorise(n / c, p, j + 1) + 1;
        }
    }
    if (factorsFound == 0) // n is prime
    {
        p[j] = n;
        factorsFound = 1;
    }
    return factorsFound;
}

同样在一个真正的解决方案中，你可能想要传递 p 的大小，这样你就可以检测你是否运行来自 space.

只是为了好玩，因为还没有其他人发布它，这里是一个非递归解决方案。其实和上面一样，只是递归变成了循环。

int factorise(int number, int p[])
{
    int j = 0;

    for (int c = 2, int n = number ; n > 1 ; )
    {
        if (n % c = 0)
        {
            p[j++] = c;
            n = n / c;
        }
        else
        {
            c++;
        }
    }
    return j;
}

我不同意 Lundin 关于递归的一些评论。递归是一种将问题分解为更简单的子任务的自然方法，但不可否认，在 C 语言中它的效率较低，尤其是在堆栈 space 方面，在这种特殊情况下，非递归版本更简单。

Answer 3

你已经在评论中被告知这个算法很差，这就是一个证据。而且您真的应该学习使用调试器：运行通过调试器可以立即显示问题所在。

也就是说，您这里的主要问题是 递归函数 return 时要做什么？。您没有问自己这个递归必须的问题，而只是按顺序继续，这显然是错误的，因为您将重复使用递归调用中已经处理过的数字。所以你必须在递归调用 factors.

之后立即添加一个 return 行

完成此操作后，还有另一个小问题（调试器会很明显），您只能搜索严格小于 n 的因子。所以你错过了最后一个质因数...

通过这 2 个即时修复，您的代码将变为：

void factors(int n, int p[], int j) {
  /// if n is divisible by c, store c, and continue with n/c
      int c;
      for (c=2; c <= n; c++) {
          if (c > n) break;
          if (n%c == 0) {
              p[j] = c;
              printf("%d has been added to p \t", c);
              printf("n has been reduced to %d \t", n/c);
              printf("j is %d \n", j);
              j++;
              if (n == c) break;
              factors(n/c, p, j);
              return;
          }
      }
  }

但是恕我直言 p[j] = c; 应该变成 *p = c; 而 factors(n/c, p, j); 应该变成 factors(n/c, p+1, j);。换句话说，您直接将指针传递给下一个 slot.

递归寻找主要因素

Recursively finding prime factors

c

recursion

prime-factoring