Why does this recursive code generate segfault?

Question

When I run the following code compiled with gcc (only the -std=c99 option is -std=c99 ) and it runs the executable, I get a segmentation error (the MSG kernel is reset).

Why is this?

 #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

There is one basic case in your recursion that you are considering. However, there are two:

• m == i : This happens when there is only one of the biggest factors
• m == 1 : This happens when the multiple of the highest value

You go into an infinite loop on m=4 and n=2 , because you are missing the second option. Here if (m % i == 0) true, therefore while (m % i == 0) m = m / i; performed. And since 4 is a multiple of 2, this cycle ends when m is 1.

With repeated recursion, you have m=1 and n=2 . This will lead to an else clause where you call count_factors again with m=1 and n=3 . This continues until the stack explodes.

Adding a second base case will fix infinite recursion:

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

Actually, you can get rid of the first case, since this is just a special case of 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); } } 

Then the program ends, returns 134046.

EDIT:

It will work faster without recursion:

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

On my machine, the recursive version takes about 9 seconds. The iterative version takes about 3 seconds.