यह रिकर्सिव कोड क्यों एक segfault फेंक देता है?

Question

जब मैं gcc के साथ संकलित निम्न कोड चलाता हूं (केवल विकल्प चालू है -std=c99) और निष्पादन योग्य चलाएं, मुझे एक सेगमेंटेशन गलती मिलती है (msgstr "कोर कोर डंप किया गया)।

वह क्यों है?

#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

आपके रिकर्सन में, एक आधारभूत मामला है जिस पर आप विचार कर रहे हैं। हालांकि, वहाँ दो हैं:

• m == i: यह तब होता है जब केवल है वहाँ सबसे बड़ा कारक के 1
• m == 1: यह तब होता है जब वहाँ सबसे बड़ा कारक के कई हैं

आप जा रहे हैं m=4 और n=2 पर एक अनंत लूप में क्योंकि आप दूसरे मामले को याद कर रहे हैं। यहां, if (m % i == 0) सत्य है, इसलिए while (m % i == 0) m = m/i; रन। और चूंकि 4 2 की एक बहु है, इस पाश खत्म हो जाएगा जब m है 1.

जब आप फिर से recurse, आप m=1 और n=2 है। यह else खंड को हिट करेगा, जहां आप count_factors को फिर से m=1 और n=3 पर कॉल करेंगे। यह तब तक चलता रहता है जब तक ढेर उड़ा नहीं जाता है।

दूसरा आधार मामले जोड़ना अनंत प्रत्यावर्तन ठीक कर देंगे:,

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 सेकंड लगते हैं।