在c中使用递归找到最大素因数

Question

已经编写了我认为是一个很好的算法的代码，用于使用递归查找大量数字的最大素因数。不过，当分配给变量huge_number 的任何大于4 的数字时，我的程序都会崩溃。我不擅长递归，并且赋值不允许任何类型的循环。

#include <stdio.h>

long long prime_factor(int n, long long huge_number);

int main (void)
{
    int n = 2;
    long long huge_number =  60085147514;
    long long largest_prime = 0;

    largest_prime = prime_factor(n, huge_number);
    printf("%ld\n", largest_prime);

    return 0;
}

long long prime_factor (int n, long long huge_number)
{
    if (huge_number / n == 1)
        return huge_number;
    else if (huge_number % n == 0)
        return prime_factor (n, huge_number / n);        
    else
        return prime_factor (n++, huge_number);
}

任何有关它为何崩溃以及我如何改进它的信息将不胜感激。

Answer 1

即使解决了使用后递增的问题以使递归永远持续下去，这也不太适合递归解决方案 - 请参阅 这里了解原因，但归根结底是减少搜索的速度 空间。

虽然 huge_number 的除法很快就能减少它，但绝大多数递归调用都是通过简单地增加 n 来完成的。这意味着您将使用大量的堆栈空间。

你会更好：

• 使用迭代解决方案，这样你就不会耗尽堆栈（如果你只是想解决问题）^(a);或者
• 如果您只是想学习递归，则找到更适合递归的问题。

---

^(a) 这种野兽的一个示例（以递归解决方案为模型）是：

#include <stdio.h>

long long prime_factor_i (int n, long long huge_number) {
    while (n < huge_number) {
        if (huge_number % n == 0) {
            huge_number /= n;
            continue;
        }
        n++;
    }
    return huge_number;
}

int main (void) {
    int n = 2;
    long long huge_number =  60085147514LL;
    long long largest_prime = 0;

    largest_prime = prime_factor_i (n, huge_number);
    printf ("%lld\n", largest_prime);

    return 0;
}

---

从该迭代解决方案的输出中可以看出，最大的因子是 10976461。这意味着递归解决方案中的最后一批递归将需要一千万个堆栈帧的堆栈深度，这不是大多数环境能够轻松应对的。

如果您确实必须使用递归解决方案，则可以利用您没有有一直检查这一事实，将堆栈空间减少到其平方根最多可达该数字，但仅限于其平方根。

此外，除了2之外，其他所有素数都是奇数，因此您可以通过仅检查两个加上奇数来进一步将搜索空间减半。

考虑到这两件事的递归解决方案是：

long long prime_factor_r (int n, long long huge_number) {
    // Debug code for level checking.

    // static int i = 0;
    // printf ("recursion level = %d\n", ++i);

    // Only check up to square root.

    if (n * n >= huge_number)
        return huge_number;

    // If it's a factor, reduce the number and try again.

    if (huge_number % n == 0)
        return prime_factor_r (n, huge_number / n);

    // Select next "candidate" prime to check against, 2 -> 3,
    //   2n+1 -> 2n+3 for all n >= 1.

    if (n == 2)
        return prime_factor_r (3, huge_number);

    return prime_factor_r (n + 2, huge_number);
}

您可以看到我还删除了（在我看来很尴尬）构造：

if something then
    return something
else
    return something else

我更喜欢来自以下内容的不太大量缩进的代码：

if something then
    return something
return something else

但这只是个人喜好。无论如何，这会让你的递归级别降低到 1662（取消注释调试代码以进行验证）而不是 1000 万，这是一个相当大的减少，但仍然不完美。在我的环境下运行没问题。

Answer 2

您的意思是 n+1 而不是 n++。 n++ 使用后 n 会递增 ，因此递归调用会获取 n 的原始值。

Answer 3

您正在溢出堆栈，因为 n++ 后递增该值，使用与当前调用中相同的值进行递归调用。

Answer 4

崩溃原因是堆栈溢出。我向您的程序添加一个计数器并执行它（在 ubuntu 10.04 gcc 4.4.3 上），计数器在核心转储之前停止在“218287”。更好的解决方案是使用循环而不是递归。