Perché questo codice ricorsivo genera un segfault?

Question

Quando eseguo il seguente codice con gcc compilato con (solo l'opzione attivata è -std=c99) ed eseguo l'eseguibile, ottengo un errore di segmentazione (core scaricato).

Perché è quello?

#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

Nella tua ricorsione, c'è un caso base che stai considerando. Tuttavia, ci sono due:

• m == i: Ciò si verifica quando c'è solo 1 del fattore di grande
• m == 1: Questo accade quando ci sono più del fattore di grande

si sta andando in un ciclo infinito su m=4 e n=2 perché ti manca il secondo caso. Qui, if (m % i == 0) è true, quindi viene eseguito while (m % i == 0) m = m/i;. E dal momento che 4 è un multiplo di 2, questo ciclo termina quando m è 1.

Quando si recurse ancora una volta, si ha m=1 e n=2. Questo colpirà la clausola else, dove si chiama di nuovo count_factors con m=1 e n=3. Questo continua finché lo stack non esplode.

aggiunta del secondo caso base risolverà il ricorsione infinita:

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

In realtà, si può sbarazzarsi del primo caso, dal momento che è solo un caso speciale di 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); 
    } 
} 

Il programma quindi eseguito fino alla fine, in uscita 134046.

MODIFICA:

Verrà eseguito più veloce senza ricorsione:

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

Sulla mia macchina, la versione ricorsiva richiede circa 9 secondi. La versione iterativa dura circa 3 secondi.