为什么这个递归代码抛出一个段错误？

Question

当我运行下面用with编译的代码gcc(仅打开选项-std=c99)并运行可执行文件时,我得到一个分段错误(msg core dumped).

这是为什么？

#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子句，您可以在该子句中使用和count_factors再次调用。这一直持续到堆栈爆炸为止。m=1n=3

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

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秒。