Dlaczego ten kod rekurencyjny generuje błąd segfault?

Question

Po uruchomieniu następującego kodu skompilowanego za pomocą gcc (włączona jest tylko opcja -std=c99) i uruchomienia pliku wykonywalnego, otrzymuję błąd segmentacji (rdzewiejący klucz msg).

Dlaczego tak jest?

#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

W rekurencji bierze się pod uwagę jeden podstawowy przypadek. Jednakże istnieją dwa:

• m == i: Dzieje się tak, gdy istnieje tylko 1 największego współczynnika
• m == 1: Dzieje się tak, gdy istnieje wiele największego współczynnika

Jedziesz w nieskończoną pętlę na m=4 i n=2, ponieważ brakuje ci drugiego przypadku. Tutaj, if (m % i == 0) jest prawdziwe, więc działa while (m % i == 0) m = m/i;. A ponieważ 4 jest wielokrotnością 2, pętla ta zakończy się, gdy m ma wartość 1.

Po ponownym powtórzeniu, masz m=1 i n=2. To trafi w klauzulę else, gdzie ponownie zadzwonisz pod numer count_factors z m=1 i n=3. To trwa, dopóki stos nie wysadzi w powietrze.

Dodanie drugi przypadek bazowy będzie naprawić nieskończoną rekurencję:

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

Właściwie można pozbyć pierwszym przypadku, ponieważ jest to tylko szczególny przypadek 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); 
    } 
} 

następnie program kończy pracę, wypuszczając 134046.

EDYTOWANIE:

To będzie działał szybciej bez rekursji:

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

Na moim komputerze, wersja rekurencyjna trwa około 9 sekund. Wersja iteracyjna trwa około 3 sekund.