c - 为什么这个递归代码会抛出段错误？

Question

当我运行以下用 gcc 编译的代码(唯一打开的选项是 -std=c99)并运行可执行文件时，我得到一个段错误(msg核心转储)。

这是为什么？

#include <stdio.h>

int count_factors(int n, int i) {
    int m = n;
    if (m == i) {
        return 1;
    } else if (m % i == 0) {
        while (m % i == 0) m = m / i;
        return 1 + count_factors(m, i);
    } else {
        return count_factors(m, i+1);
    }
}

int main() {

    int streak_size = 4;
    int streak = 0;
    int solution = 0;
    int n = 2;

    while (solution == 0) {
        n += 1;
        int c = count_factors(n, 2);
        if (c == streak_size) {                  
            streak += 1;
        } else {
            streak = 0;
        }
        if (streak == streak_size) solution = n;
    }
    printf("%i", solution);
    return 0;
}

Answer 1

在您的递归中，您正在考虑一种基本情况。但是，有两个:

• m == i:当只有 1 个最大因子时会出现这种情况
• m == 1:当有多个最大因子时会发生这种情况

您将在 m=4 和 n=2 上进入无限循环，因为您错过了第二种情况。此处，if (m % i == 0) 为真，因此 while (m % i == 0) m = m/i; 运行。由于 4 是 2 的倍数，因此当 m 为 1 时，此循环将结束。

当你再次递归时，你有 m=1 和 n=2。这将命中 else 子句，您可以在其中使用 m=1 和 n=3 再次调用 count_factors。这一直持续到堆栈爆炸。

添加第二个基本情况将修复无限递归:

int count_factors(int n, int i) {
    int m = n;
    if (m == i) {
        return 1;
    } else if (m == 1) {
        return 0;
    } else if (m % i == 0) {
        while (m % i == 0) m = m / i;
        return 1 + count_factors(m, i);
    } else {
        return count_factors(m, i+1);
    }
}

实际上，您可以去掉第一种情况，因为它只是 if (m % i == 0) 的一个特例:

int count_factors(int n, int i) {
    int m = n;
    if (m == 1) {
        return 0;
    } else if (m % i == 0) {
        while (m % i == 0) m = m / i;
        return 1 + count_factors(m, i);
    } else {
        return count_factors(m, i+1);
    }
}

然后程序运行完成，输出 134046。

编辑:

如果没有递归，它会运行得更快:

int count_factors(int n, int i) {
    int m = n;
    int total = 0;
    while (m != 1) {
        if (m % i == 0) {
            while (m % i == 0) m = m / i;
            total++;
        }
        i++;
    }
    return total;
}

在我的机器上，递归版本大约需要 9 秒。迭代版本大约需要 3 秒。