なぜこの再帰的コードがセグメンテーションを投げるのですか？

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; 
} 

Answer 1

あなたの再帰では、あなたが検討している1つのベースケースがあります。しかし、2つがあります。

• m == i：のみ
• m == 1最大の要因の1がある場合にこれが発生します。これが最大の要因の倍数である

あなたが行っているときに発生します2番目のケースがないため、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=1とn=3と表示されます。これは、スタックが爆発するまで続きます。

第2のベースケースを追加すると、無限再帰を修正します：それはちょうどif (m % i == 0)の特殊なケースだから

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); 
    } 
} 

は実際に、あなたは、最初のケースを取り除くことができます。

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秒かかります。