2

已经编写了代码，我认为这是一个很好的算法，可以使用递归找到大量的最大素数。我的程序崩溃，但分配给变量 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);
}

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

4

4 回答 4

1

你的意思是n+1代替n++. 使用后自n++增，所以递归调用得到 的原始值。n n

于 2012-01-30T02:26:58.627 回答
1

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

于 2012-01-30T02:28:23.943 回答
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（取消注释要验证的调试代码）而不是一千万，这是一个相当大的减少，但仍然不完美。在我的环境中运行正常。

于 2012-01-30T02:52:01.840 回答
0

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

于 2012-01-30T04:23:11.163 回答