Bu özyineleme kodu neden bir segfault atıyor?

Question

gcc ile derlenmiş olan aşağıdaki kodu çalıştırdığımda (yalnızca seçenek açık -std=c99) ve yürütülebilir dosyayı çalıştırdığımda, bölümleme hatası (msg çekirdek dökümü) alıyorum.

Neden?

#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

Sizin özünde, düşündüğünüz bir temel durum var. Ancak, iki vardır:

• m == i: Sadece
• m == 1 büyük faktör 1 olduğunda bu oluşur: Bu orada büyük faktörün birden olan

Gidiyorsunuz ne olur m=4 ve n=2 üzerinde sonsuz bir döngü içine, çünkü ikinci durumda eksik. Burada if (m % i == 0) doğru, bu nedenle while (m % i == 0) m = m/i; çalışır. Ve 4, 2'nin katları olduğu için, m 1 olduğunda bu döngü sona erer.

Tekrar tekrar açtığınızda, m=1 ve n=2 var. Bu else yan tümcesi, count_factors yeniden m=1 ve n=3 ile çağıracaktır. Bu, yığın havaya uçana kadar devam eder.

ikinci baz durumda ekleme sonsuz yinelemeye çözecektir: Bu if (m % i == 0) sadece özel bir durum olduğundan, aslında

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

, ilk durumda kurtulabilirsiniz:

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

program tamamlandıktan sonra 134046 çıktısı alır.

EDIT:

Bu özyineleme olmadan daha hızlı çalışacak: my makinede

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

, özyinelemeli sürüm yaklaşık 9 saniye sürer. Yinelemeli sürüm yaklaşık 3 saniye sürer.