为什么这段递归代码会抛出segfault错误？

Question

当我运行以下代码并使用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;
}

- user3597931

---

在count_factors中，由于您从未退出递归，因此请在count_factors函数开头添加printf("%d %d\n", n, i);，您就会明白了。 - Jabberwocky

哦，讽刺啊，在一个叫做“StackOverflow”的网站上。 - Wim

编译时应始终启用警告，例如-Wall。请注意，这是一般建议，可能无法帮助解决您特定的问题。 - Klas Lindbäck

当然，简单的调试无法检测到逃逸递归... :(( - Martin James

嗨，我想检测像这样的无限递归错误落在停机问题上，所以编译器不可能检测到吗？还是我夸大了？ - user3597931

Answer 1

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

- `m == i`：当只有一个最大因数时发生 - `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秒钟。

- dbush